Does it specifically state that your iCloud storage is full, or that you cannot backup because there is not enough space in iCloud?
If it states your iCloud storage is full, trying logging into iCloud.com from a computer and checking your Photos from there. If you turned off iCloud Photos prior to deleting, the Photos may not have deleted from iCloud and you may need to delete manually from iCloud.com. Also make sure you check the ‘Recently Deleted’ folder in Photos to ensure you delete from there was well, otherwise the Photos will continue to use space.
If you are getting the message that you cannot backup because you do not have enough space, you will likely need to do one or both of these things:
- Upgrade your iCloud storage
- Cleanup/reduce your internal iPhone storage