Android Auto abschalten hatte ich auch versucht, das hat nichts gebracht, Bluetooth und mobile Daten waren natürlich angeschaltet, daran hat es nicht gelegen.
Inzwischen scheint es bei mir auch zu funktionieren, ich hatte erst auf dem Smartphone der My BMW App die Berechtigung zum Start im Hintergrund gegeben und dann das Smartphone entkoppelt und neu verbunden. Jetzt wird auch direkt nach dem Drücken des Start/Stopp Knopfs verbunden.
Da ich das Smartphone auch schon vorher schon ein paar mal entkoppelt und neu verbunden habe, vermute ich dass die My BMW App doch irgendwie bei der Verbindung beteiligt ist, WLAN scheint da auch im Spiel zu sein. Nun ja, jetzt funktioniert es jedenfalls. Danke für alle Tipps.