I know this is an old topic, but it's currently the first result on Google for this issue so I figured I'd add what fixed this for me:
When I first set up Android Auto, I didn't activate the "Wireless Android Auto" permissions in the GrapheneOS settings for it, because my car doesn't have wireless AA. Apparently that setting is required to manage bluetooth connections.
What I did to fix this issue:
In:
Settings App > Apps > Sandboxed Google Play > Android Auto
Enable the following setting:
Allow permissions for wireless Android Auto
Hopefully this helps someone else to resolve this confusing issue.