Auch die Config App verwendet? Kein VPN eingeschaltet! (das hatte ich mal versehentlich angelassen, dann erfolgt keine Verbindung).
Wichhtig ist noch, dass in den AA Einstellungen der Punkt "Kabelloses Android Auto" eingeschaltet ist. Dieser Punkt erscheint in den Einstellungen evt. erst, nachedem man die Entwicklereinstellungen aktiviert und dort das Häkchen gesetzt hat bei "Kabellose Projektion zu den Einstellungen hinzufügen".
Entwicklereinstellungen werden aktiviert, in dem man in den Android Auto Einstellungen auf den untersten Punkt mit der Versionsinfo einige Male hintereinander draufdrückt. Dann hat man oben rechts unter den 3 Punkten die Entwicklereinstellungen.