Just trying to help debug things. The only Mercedes that I can use as a reference is an older model. I have successfully used my 4.4.2 phone with several vehicles, so I'd like to get a handle on where the problem is to help offer a solution.
I may have fixed my problems - I've had bluetooth working in my car (2012 BMW I-Drive Nav) for the past 2 days, My HTC One with 4.4.2 OTA pairs as soon as I start my car, my contact list loads up within 3 minutes, my inbound and outbound call history appears, and my emails are copied to my car for voice translation.
i think the problem was duplicate google contacts. For some reason, I had 2-3 duplicates of all my goggle contacts on my cellphone, all probably caused by failed sync sessions. I looked at my linked contacts setting under the contact list menu and manually deleted 344 duplicate google entries from my cell phone. I took the phone back to my car, started it up, and to my surprise, the contact list loaded up quickly.
Previously, my bluetooth would pair with my car, but would unpair after 5 minutes while trying to download my contacts. It would disconnect after 1 minutes while in a call but also while trying to download my contacts. Now that it's able to download my smaller contact list successfully, it stays paired and I have not had any disconnects while in conversation.
Hopefully, it stays fixed. If it doesn't, then my next step is to delete my Facebook and Linked In contacts which I really don't need. Give this a try. Perhaps it will work for you as it did for me.