M
Hello, I just spent hours trying to fix mine and resolved it. I thought I would share my experience. After I cleared cache, force stop android device manager and still receive the pop up. I looked at my settings and clicked apps to see if there was still google play service. If not download it by google search for the apk and once you dl it you will have to allow unknown source dl in your settings to install the apk (dl at your own risk). After it is installed. Turn off your phone by clicking the power off. Then after a few seconds to a minute turn it on. It might pop up saying optimizing apps, leave it alone until completely back to main screen. Everything should work now.
If that did not work I would try to uninstall google play service (note not google play store). I would also install it again and follow what I mentioned above. I hope it helps. Powering it off and back on is an important step. Do all this at your own risk. I honestly didn't lose anything doing this and in fact everything was back to normal just with a new OS (marshmallow android 6.0 in my case).