Solved
de0u
No, didn't save any links, I found some discussions with similar to identical symptoms.
But, I found the solution.
I connected the 7a by wire to the USB-A of the car radio, started Android Auto on the radio, aaand suddenly the phone paired via BT. Tadaaa.
This may not be a bug, this even could be a security feature, not of the radio, but of GrapheneOS. Because the wired connection must have established some kind of communication between the devices that finally allowed BT pairing. This is just a guess, but plausible.
Now the 7a is BT paired and connects just fine without Android Auto. AA was just needed once for the wired connection and BT pairing.
Thus, I just had to install Android Auto on my 7a (in my google´d 2ndary profile) and connect first with a USB-C to USB-A cable.
Hope it helps someone else.