Reading your question, I can assume you are a little bit experienced with android. Now, here is the answer: Your Google play store/services will keep popping that error message because they are not up to date. On top of that, many apps might(and ideally should) have stopped working and would show you the error that appname has stopped working. The reason is same - Google play services are not up to date.
Solution: When you want to update an app normally, you go to play store, but here it is not possible. You have to flash G-apps manually. I would suggest you download the zip file from here: Open Gapps
G-apps are nothing but few mandatory Google apps. This would not reset anything or you would not loose any data at all. Factory reset is not required.
Background: Updated version of android (say Marshmallow) would not work with the google play services of its predecessor(play services of Lollipop). This is exactly what happened in my case a couple of days back. I flashed new custom ROM with old Gapp package(of Lollipop version), because I was so lazy to download new Gapp package :) . Hence I was facing that irritating error message every 5 seconds.
Hope you have found the answer useful!