"Optimise Mac Storage" not working

You wrote - However, there's still 30+ GB free on iCloud, and only <1GB free on my MacBook Air.

It means there is sufficient space on iCloud but less space on hard drive see the thread https://discussions.apple.com/thread/251789307

Also - For some reason, my files aren't being deleted off my MacBook to be stored exclusively on iCloud like they're meant to be ===make sure iCloud Drive and desktops and documents box is turned as on https://support.apple.com/en-us/HT201104

Read https://support.apple.com/guide/system-information/find-and-delete-files-syspf5a64aa6/mac

Greetings, stephenpaull17.

It appears that you're having a problem freeing up storage space on your Mac. You're optimizing the storage space on your Mac by moving documents to iCloud Drive. You're also trying to optimize storage for your photos and the songs you have in iTunes. We understand how important it is to have sufficient space on your Mac, and we're glad to help with this.

How to free up storage space on your Mac - Apple Support -- When you begin storing your documents in iCloud Drive, you should see a folder named "Desktop and Documents" on the Desktop of your Mac. Any files that have been synced to iCloud Drive should be viewable in Finder under iCloud. If you're not seeing them in iCloud Drive, go to the Apple Menu > System Preferences, and select your Apple ID. Make sure that iCloud Drive and Photos have both been selected. Then check which options you've selected beside iCloud Drive. If you see your files in iCloud Drive, delete one document from your Mac (not one included in “Desktop and Documents though) then double-check iCloud Drive in Finder to view the document is still in iCloud Drive. If it’s still there, remove the remaining documents from your Mac.

Turn on Sync Library with Apple Music - Apple Support -- If you don't subscribe to Apple Music, you won't be able to use iCloud to store your music. If you've turned it on, open iTunes, and select from the menu bar iTunes > Preferences and turn off "Sync Library" if it's on. If you do subscribe to Apple Music, you should see a cloud with a downwards arrow indicating that it's stored in iCloud.

Let us know how that goes.

Take care.

Thanks for getting back to us with more information, stephenpaull17. It's appreciated. At this point, we'd like you to contact Apple Support to guide you through the process.

Get Support -- After selecting this link, choose whichever model of Mac you're using. Type "storage" in the Search topics field, then select "Device storage is almost full" from the results.

Cheers!