I have now been able to get my 5200 to connect to my Pixel 6 Pro (Android 15) via Bluetooth. In my case it involved a factory reset of the 5200 but I suspect that this was not necessary since the "logic" behind how the TomTom connects seems a bit out of sorts when it has a choice, something that I had not noticed before I started looking into this closely. There is also a potential gotcha on the phone.
On your phone, first of all make sure that Bluetooth tethering is enabled. On stock Pixel Android 15 this is under Settings - Network and Internet - Hotspot and tethering - Bluetooth tethering.
Gotcha: The default appears to be off, plus there are reports in the Android forums of this turning itself off at random. I have seen this but not since I have made a successful data connection.
Remove any previous attempt from your phone at Bluetooth pairing of your TomTom. I don't think this is necessary but it's a quick way of having the phone forget any prior settings related to the TomTom and cannot hurt.
Now disable (forget) any active WiFi settings on the TomTom or configure the Bluetooth settings away from a known access point.
Gotcha: If WiFi is present and connected, the TomTom seems to stop trying to connect via Bluetooth. This is not a problem once it is set up (in fact it's probably preferable), but it completely stopped me from making that initial connection so it looked like data over Bluetooth just did not work when it does. Arguably in this configuration the error message on the TomTom saying that data over Bluetooth cannot be established is incorrect, something like "Using WiFI" would be better. It is even more confusing because the TomTom says it can connect for voice and messaging over Bluetooth.
Now, on your phone, go into Settings - Connected devices and "Pair new device".
On the TomTom, go into Settings - Bluetooth and "Add phone". Watch your phone and when the TomTom appears in the list of available Bluetooth devices, select that.
When prompted to confirm the pairing request, I made a point of confirming it on the TomTom first, then the phone - I am not sure but when I was trying to get this to work it appeared that if I confirmed it on the phone first it did not work.
From here you can change the Bluetooth features such as disabling calls and messaging. I use the hands-free kit that is a standard factory fit in my car, so I have turned these off but left the data enabled.
And that's it. However - one gotcha remains.
The TomTom only updates its traffic every few minutes. If the TomTom has updated recently (either by the on-board SIM or WiFi), it can take several minutes before any changes you have made regarding Bluetooth may be evident. This caught me out and led me down the wrong path on a few occasions because the Bluetooth data status does not update in between.
Once the TomTom has made its first connection over Bluetooth tethering the presence of WiFi does not seem to be an issue. For example, when I drive off from home / work my TomTom can connect via WiFi. However once I am on the road and out of range, it connects quite happily over Bluetooth (no need to remove the SIM, the logic here appears to favour a Bluetooth connection over the internal SIM). The TomTom also reconnects to WiFi on its own when in range.
Just a reminder - on the 5200 at least the SIM can be removed without dismantling the device. It is behind the small ID sticker next to the microSD card slot that can be lifted using a pair of tweezers. The SIM just pulls out (don't try pushing it in and hoping that it will pop out) but does also require tweezers in order to catch the edge.
I hope that this helps someone else who may be having difficulties in connecting to the TomTom services over Bluetooth.