I bumped into something that may help. I visited a friend that had trouble connecting her brand new Huawei phone to her older Nissan car audio system. This may seem of topic but something tells me it may not be.
I was able to solve her problem by adding an option to the APN type setting on her phone.
You can find this setting by going into settings, connections, mobile networks, access point names, tap on the provider name to access the APN settings for your provider and scroll down to access point type (translating from Dutch, so it might actually be slightly different on your phone).
To help my friend I added the dun option, which should be obsolete on modern devices but it helped (source:
https://tamingthedroid.com/apn-type).
Adding options to the APN type on your phone tells your phone which protocols can be used for making a connection with another device, e.g. for Bluetooth tethering.
My Samsung Note 8 connects flawlessly with my Galaxy watch. The APN type says "default, supl" (without the " " but with the comma, which is used to separate the options).
I think it is worth checking the APN type settings on your phone and set it to the settings mentioned if it is different.
For my Note 8 I can remove either of them without it failing to connect to my watch, but that may depend on the hardware / firmware.
So .... try and see what happens?