NOTE: I just wanna share my experience in case someone might need it. I’ve already solved the problem.

I had a problem where I disabled the sync of my Photos to the iCloud and after trying to enable it again, an insufficient storage error pops up.

After some debugging, I realized that iCloud also keeps the deleted pictures—contributing to the apparent storage shown on the pop-up error. Thus, I deleted all images in my Recently Deleted album and tried syncing it back in again. Gladly, it worked.

I hope this message could help you in any way :))