Paid for more storage and still get the "full" message on my iPhone

You are under the mistaken belief that paying for more iCloud Storage gives you more storage on your iPhone. It does not, because it cannot. Buying mores space in the cloud, let's you sync more data with the cloud, such as photos, messages, backups, etc. It does not increase the space your phone as there is no way to increase the physical memory on any iOS device.

If you are out of space on your iPhone, you'll have to delete things you don't need or use, which can include Photos, Music, Apps, Files, Messages, Email, etc.

Read this link about the difference between iCloud and iPhone physical storage --> What's the difference between device storage and iCloud storage? - Apple Support

And here is some more information, you might want to read --> How to check the storage on your iPhone, iPad, and iPod touch - Apple Support

Again, there is no relation between the physical storage on your device and the storage you have in iCloud. Go to Settings > Your Name, Apple ID, iCloud, etc . > Tap iCloud > What does it show at the top in terms of Storage in the Cloud? Example, 32 GB of 50GB Used.

Post that back please.

Okay so what about when you do have iPhone storage but you don’t have iCloud storage although you purchase storage every month and there is no difference with the message being “iCloud storage full”?