Ese problema lo llevo teniendo yo ya mucho tiempo. Algunas veces esperando se descargaban, o utilizando otra red Wi-Fi.
Aunque la solución que siempre funciona es descargar e instalar directamente las apk de las GApps desde apkmirror; Primero el marco de servicios de Google, segundo los servicios de Google (Estas dos son diferentes, es muy importante que instales la primera), y por último el Google Play Store
