Have you tried a different cable? I've had issues similar to yours with mine and a new cable sorted it.Still having issues with Android Auto after all this time. Regularly receive a message that I can't use it with the cable I have, but restarting the phone fixes the issue everytime so it's not the cable. Never happened with any of my Samsung phones or my wife's S10 in the same car (Zafira).
Is a lottery when I plug my phone in if it will decide to work that day or not. Not the end of the world I know but always decides to go up the creek when I'm late or in a rush...
I think I also cleared the data/cache from my android auto app and set it up fresh again. Have you done that?