Why does my iPhone keep saying I don't have enough storage?

Check Settings ➜ General ➜ iPhone Storage and tell us what it says there.

Also, what exactly did you pay for?

If you paid for iCloud Storage, then it has no effect on your iPhone's local storage capacity.

click here ➜ What's the difference between device storage and iCloud storage? - Apple Support

What do you mean by 'paid double'?

Every iPhone comes with a fixed amount of storage. It can't be updated. If your profile is correct and you have an iPhone 12, there were options for 64GB, 128GB, or 256GB.

Once the phone gets full, there are a number of options Apple offer to 'offload' lightly used content such as old photos, apps, etc. to iCloud, automatically retrieving it when you need it.

This is controlled via Settings -> iCloud -> Storage where you can choose what content to offload. If you haven't enabled this, try it now to see if it frees up enough space on your device.