Update: there is no problem, at the end. I have realizeed that Google garbage framework does not get automatically updated, same for Android Auto. I use multiple profiles, which complicates things a bit - because I do not install that spyware anywhere except a dedicated profile for the apps that cannot live without GSF. So, there was an update for both frameworks. I have installed them during the day and I was able to successfully use Waze on my way home. Bottom line: either because of something expiring or because the recent GrapheneOS updates, older versikn of Google Auto stopped working, buy the updated one works.