Phone GS290
Android 11
/e/ OS 1.13-r-20230724313393-stable-GS290
I don’t think it’s due to the Android version and / or OS version as before it was Android 10 and older OS versions like 0.8. Each time I get a new version, I tried to link the GS290 to my car without any success.
Moreover, no problem to link my GS290 to my Mazda MX5 or the Jeep Renegade of my wife. And other smartphones can be linked to my Mazda CX30.
I was able to successfully pair my phone (FP3+) with my car (Mazda3), which has the same software (Mazda Connect) as your car. So it should work for you too.
Perhaps you could try deleting the pairing on both your phone and your car, so you can re-pair again.