I have a 2018 Ford Explorer Platinum running the Sync3 infotainment system. I had no problem plugging in and getting Android Auto until the February 2022 security update. That broke it. As stated, I can unplug my Z Fold 3 from the cable, immediately plug in my Darling Bride's Note 10+ and Android Auto starts right up. That eliminates the head unit and cable, leaving only the phone.
A quick look in the Samsung Members app Community shows dozens of users, all owning newer model Galaxy phones, experiencing the same problem. I sideloaded the Android Auto 7.7 version that fixed the S22... it doesn't fix the Z Fold 3. Now I'm on the very latest: the 7.8.1223 beta and it doesn't work. Of course, sending error reports and log files to Samsung is an exercise in futility because the files don't show enough data. They keep wanting me to set the logger buffer size to 16MB - but the Z Fold 3 has a maximum buffer size of 8MB.