The message of needing more storage to perform an update is for device storage, not iCloud storage. You can use iCloud storage to ease some storage constraints on your device when using Optimized Storage, but it certainly is possible to not have enough device storage even when there is available iCloud storage space. This support article will help explain the difference:
What's the difference between device storage and iCloud storage? - Apple Support
If you are already using Optimized storage for you photos along with iCloud Photos, then usually it is the apps installed on your device that is taking up the device storage space. If allowed apps can be offloaded when space is constrained, but they are not stored in iCloud and the data those apps used are still stored on your device unless that app is actually deleted.
To check the device storage available, you would go to Settings > General > iPad Storage. Another way that an update can be performed on an iPad is when you connect it to a computer if you have one available. When connected to a computer the update does not have to be first downloaded to your device and then install from there, where additional storage space is needed.