Play Store lädt nichts herunter

Hallo,
Der PlayStore lädt bei mir nichts herunter bzw. sehr verspätet. Wenn ich eine App herunterladen will, dann bekomme ich nur die Meldung "Wird herunterladen...". Wenn ich eine neue App herunterladen will, dann muss ich Abends den Download beginnen und mit Glück ist die App morgens heruntergeladen.
Ich habe schon vieles versucht, um diesen bug zu fixen.
Was ich versucht habe:
- Gerät neu starten
- Cache vom Playstore leeren
- CCleaner durchlaufen lassen
- Playstore Updates gelöscht
- Android neu aufgesetzt

Das hat aber alles nichts gebracht. Selbst nachdem ich die Playstore Updates gelöscht habe, hat es einige Tage gedauert bis die Updates sich von selbst Installiert haben.
An meiner Internetleitung kann es übrigens nicht liegen, die ist schnell genug.

Es wäre echt schön, wenn mir geholfen wird.
Vielen Dank.

Asus Zenfone 4 Max mit Android 7.1.1