So I deleted apps and added storage
The message applies to the Device... Not iCloud. Increasing iCloud Storage does Not Increase the storage capacity of the Device.
You need to Delete Content from the Device... at least 3 GB of Free Space is required to update. ( if that is what you are attempting to do.)
Once Updated... Re-Sync your Content.