I've got a GS5 on Sprint with AVIC-8100NEX. On the stock rom I got the following message: "Cannot support Android Auto Your device cannot support Android Auto."
I was on the 5.0 OTA rom rooted. I flashed CM12 and now everything is working as expected! I was able to make and receive calls, use Google maps, Navigation and Voice search.