I don’t know, how to remove the entire device.
Now I enabled in Settings > Systems > NFC > Buetooth Secure Simple Pairing (which was diabled by default)
Now the pairing worked at once.
Further test:
NFC disabled completely, disabled Bluetooth for short, enabled Bluetooth again
→ next pairing works (even with disabled NFC)
(Perhaps this enabling “Buetooth Secure Simple Pairing” helps in a car, too.
EDIT: It doesn’t improve the connection in my car.)