So, ich habe den Grund gefunden und wollte das hier teilen:
Und zwar haben die Energiespar Einstellungen des Handys die Trennung verursacht.
Lösungsweg: Android Auto muss in den Einstellungen aus dem Energiemanagement herausgenommen werden. Am besten auch Spotify und Maps.

Danach hat es normal funktioniert.

Danke allen für die Hilfe!