I have been using Galaxy S4 for past 6 months, satisfactorily. Recently, after pairing my device with a new HP3545 E-Printer, HandsFree mode (HFM) activates automatically on my device. Even after disabling it, HFM gets activated repeatedly. I have un-paired my device with this printer, but the problem still remains.
Have you checked that you don't have any 'car' locations saved? I remember that after I paired my phone with my car audio system, it would record that as CAR, and every time it even saw the bluetooth connection available, even if it didn't pair, Car Mode kicked in. You just disable the location option and that's it.
Another possibility, if this happens randomly, is that your USB port is damaged or dirty and a false contact might be triggering Hands Free Mode as if you were plugging in a car dock. This happened to me on an S3, so I know it's a possibility.
If anything Spook Droid said doesn't fix it, it's 6 months old, so it's still under warranty. Bring it in for a free repair or replacement. (Make sure everything is backed up.)
