Android Auto does not navigate
issuetracker.google.com
issuetracker.google.com
Turns out: Google! There is a known issue - now ongoing for over a month - that prevents users from starting navigation using the assistant.
The workaround? Unplug the device, set the destination on the phone, plug it back in. Now, try that with wireless Android Auto.