Just to finalize this:
I could solve the issue, with the help from Phillip in the German DP.
After I cleaned-up the permissions, I always used to set COARSE and FINE location both, I've set to COARSE location only,
which I was sure that this is good enough to start Bluetooth.
But that was a wrong assumption, as the Android documentation tells me here:
The strange thing was that BLE started anyhow ignoring that it was not allowed to, after an external permission change back and forth,
while I expected a sudden, startup crash (as usual with permisson issues), when touching any of these dangerous APIs.
Never saw such half-allowed states before, and I still think this is a kind of Android bug.
Maybe I've got used to sudden, startup crashes so much meanwhile, that I don't think twice when they not appear .