I’m happy to announce that I was able to pair (and then successfully connect, including full sync of phone book, call log, etc.) both the X10 III and the XA2 Ultra (both running 4.4.0.68) with all the car kit units I own, i.e. 5 units in total (2 mounted in two cars, and three as spare parts).
It had to be done entirely via the terminal using bluetoothctl. The important part was that after issuing the pair command and entering the PIN code upon request, one has to either patiently wait for the device to reconnect or connect it manually using connect [mac address] command, and as soon as it is connected quickly issue the trust [mac address] command. Then, after successful trust'ing, if devices disconnect, it takes quickly issuing connect [mac address] command again to promptly reconnect, after which the devices start exchanging information about available Bluetooth profiles, which makes the whole pairing process complete and correct. After that, synchronising phone book and call log starts automatically.
Clearly, is all about correct order and correct timing, which (in addition to no request for the PIN code) doing it from the Settings / Bluetooth screen clearly doesn’t provide. So it is necessary to do it using bluetoothctl via the terminal, and with very precise order and timing. Not too quickly (because the car kit doesn’t seem to be a speed champion and if it gets a new command before completing the previous operation then pairing breaks) but also not to slowly or else there are clearly some timeouts which break pairing, too.
Anyway, now I have both my SFOS phones correctly paired and fully working with all my units. And they even autoconnect each time without any issues. Hooray!!!