My car allows for Bluetooth pairing with my phone, through another way in the same multimedia system (ie separate from Android Auto).
I have no idea on how to make Android Auto to work over a Bluetooth link, nor on how to debug what is wrong/missing.
[EDIT]
I just found a FAQ on my car's manufacturer website providing the steps to pair the multimedia system with Android Auto wirelessly, the exact steps I couldn't make work in my car.
To be precise, that special "wireless" button on the wheel exists on my car, but pressing it at the right time doesn't yield anything.
TL; DR: Everything weights in the way of my car supporting wireless Android Auto, nothing weights the other wya, yet it does not work and I do not know how to debug that.
Any steps to follow to achieve that?