Hat sich anscheinend gelöst.
Habe in der Google Cloud Console die Beschränkungen des
API Keys mal
rausgenommen, dann ging nach ein paar Minuten auch in der vom Play Store installierten
App die Kartenanzeige wieder.
Habe dann zuerst die Beschränkung auf "Maps
SDK for Android" wieder reingenommen,
später dann nochmal neu die Beschränkung auf "Android-Apps" mit Paketname und
SSH1 Schlüssel angelegt.
Momentan funktioniert die Kartenanzeige immer noch.
Keine Ahnung warum, SHA1 und Paketname habe ich unverändert wieder reinkopiert...
Falls es wieder nicht geht weiß ich ja jetzt wo ich dran schrauben kann.