So the Mercedes Me app is a tad bit buggy, for sure. What I do is fire it up on my phone, enter my code, select remote start and it either says it started immediately, or says it can't start or hangs. then I force stop the application, reopen, and it usually works second time. It also gets flagged on my Samsung S8 maintence app as a high battery user, since once it starts the car it seems to always be 'on' or searching or somesuch. So I force stop after I get in my car.
I find it invaluable tool in a hot climate. Go inside for an hour, say at a gym or restaurant for lunch, fire it up 10 minutes, and when I arrive at the car is cool as the other side of you know what.

 

I have restarted the app many times, reinstalled the app too, restarting the app works once in a while. I'll have them look at this issue at the next service appointment.