Well, now that still nobody responded, I decided to try a chat with Apple support, and here are my findings, for those who might run into the same problems now or in the future. Apologies in advance, I'm not a Mac specialist (yet?), so I will probably provide information that is obvious for more experienced users:
- the backup volume that I used was formatted as journaled, but not encrypted.
- support recommended to re-format it, journaled and encrypted. I did so.
- When mounting the newly formatted drive for the 1st time, Mac OS asked for the password that I specified during formatting the drive (which seems OK to me).
- I confirmed to store the PW in the Keychain app.
- (small sidestep into keychain management on the Mac (which felt/feels quite confusing to me): after storing the PW in the keychain, it apparently always instantly unlocks the drive on this very computer, where the PW got stored in keychain. This is very convenient but made me nervous in the beginning. Why was the volume always unlocked, immediately after mounting it? To test what's going on, I deleted the entry in keychain, re-mounted the volume and voila - got asked again to specify the encryption password (and to store it again in keychain)) - very convenient, once you figured out.)
- I selected the volume as Time Machine backup volume in TM settings, encrypt ON (it was on by default) and started the first backup. It completed successfully.
- then I unmounted the volume, updated a small Excel-file, re-mounted the volume again (no PW required ;-)), and started another TM backup.
- It said "encrypted" while running (in TM system settings) and completed in less than a minute.
So the trick is to encrypt the TM volume on the Mac OS level first, before using it for TM. If you don't encrypt it in the OS, but in TM only, it might take forever.
Why TM settings offers a switch for encryption yes or no, I do not fully understand. Maybe to make an encrypted backup on an unencrypted device that already contains other data that's supposed to remain unencrypted? Who knows.
I also don't know why Apple doesn't make users aware of OS encryption first. At least I did not run into such instructions when trying to resolve my problem. Maybe well hidden somewhere.