iCloud storage and iPhone storage are two separate things, and purchasing iCloud storage will not increase the iPhone storage making you able to update your device. iPhone storage is on the phone and is what is needed if you decide to update OTA. iCloud storage is just a place to store things other than on your iPhone.
If you cannot remove enough content to update the device OTA, then connect it to the computer and the latest version of iTunes and update that way.