Mein Ursprungsproblem ist gelöst. Auch mit China-Kabel funktioniert Android Auto jetzt.
Das einzige was ich tun musste, war neben der AndroidAuto App (mit der es ja teilweise bis zu 2min funktioniert hat) auch die AndroidAuto-App for Smartphones zu installieren. Jetzt ist alles stabil, so wie es sein soll. Da kommt anscheinend irgendein Stück Software mit, die erforderlich ist.