Android Immer wiederkehrendes Popup - Gerät infiziert?

anonym1

Ich besitze ein Android-Smartphone von Samsung (Galaxy S III Mini). Seit gestern oder so poppt bei mir auf dem Bildschirm immer wieder so eine Meldung auf:
"Your Google Play Store ist not setup or available, press OK to continue."
So oft und aufdringlich, wie es kommt, erscheint es mir schon ziemlich verdächtig. Zumal ich beim normalen Google Play Store, wenn ich darauf klicke, nichts Ungewöhnliches feststellen kann.
Wenn ich auf "OK" klicke, kommt dann: "Zum Aufrufen dieser Inhalte musst du dir eine Webbrowser-App installieren und einrichten."
Abgesehen davon, dass ich schon zwei solche Apps habe ("Internet" und Google Chrome), schrillen da bei mir sozusagen die Alarmglocken, weil sich das doch auch danach anhören könnte, dass ich mir etwas auf mein Gerät installieren sollte, das Schadsoftware beinhaltet... Deswegen gehe ich an dieser Stelle auch erstmal besser nicht weiter.
Wenn die Meldung auf dem Bildschirm erscheint, ist er auch komplett gesperrt, ich kann sonst nichts anklicken - mit ein paar "Wischern" bekomme ich das dann weg und alles läuft wieder, aber es kommt andauernd und das nervt.

Habe mir darauf mal Malwarebytes für Android geladen und schon zwei Mal durchlaufen lassen, aber beide Male wurde nichts gefunden...

Hat jemand eine Idee, was das sein könnte? Am Ende doch etwas Seriöses von Google Play Store? Wenn nicht, wie kann ich das los werden?