I read that warning as storage on your device, not iCloud storage.
Urquhart is interpreting the message correctly. One simple way to recover storage space on your iPhone is on the iPhone Storage window, select a seldom used application and instead of
Deleting it,
Offload it. This will retain the application data but delete the application itself. How much net memory gain you will see depends on the application. The app can always be downloaded from the App Store the next time is is needed.
There are several tricks available to reduce storage space requirements on iOS devices and transfer part of the storage load to iCloud but all impose at least some limitations/restrictions. Whether or not they are noticeceable depends on you normal usage pattern. If you are interested let me know and I will take a shot at listing them.
