"your iphone has never been backed up to icloud"

Backing up to the cloud and backing up to your computer's iTunes are two separate things, they are different ways/places to backup to : About backups for iOS devices - Apple Support. If you also want to back up to the cloud (iCloud backups are automatically encrypted) on the phone go to Settings > name (top or Settings) > iCloud > iCloud Backup > Back Up Now

So when you backup to iCloud from device's own Settings are those backups always encrypted by default?

Yes, from the link in my first reply :

Always encrypts your backups

For the watch : Back up your Apple Watch - Apple Support

Apple Watch content backs up automatically to your companion iPhone, so you can restore your Apple Watch from a backup. When you back up your iPhone to iCloud or iTunes, your iPhone backup will also include your Apple Watch data.

Here's what your Apple Watch backup includes:

Health and Fitness data, such as history, achievements, Workout and Activity calibration data from your Apple Watch, and user-entered data (To back up Health and Fitness data, you need to use iCloud or an encrypted iTunes backup.)

Yes I know that there are different ways to back up my iPhone, thing is I've now done several iTunes Encrypted Backups TO THE ICLOUD... See settings below...

No you haven't, you've done encrypted backups to your computer's iTunes. Backups to the cloud can only be done directly on the device via Settings on it. The 'Encrypt iPhone backup' on your first screenshot applies to the 'This Computer' heading directly above it, the option doesn't apply to iCloud backups, they (if/when you do an iCloud backup directly on the device) are automatically encrypted.

However after completion of each Backup (which takes over an hour each time) I still get THIS message afterwards... In other words "Your iPhone has never been backed up to iCloud"...

Only doing backups to your computer's iTunes won't change that, if you want an iCloud backup you need to go into Settings > name > iCloud on your phone and do a backup.