I don’t have a Samsung, but check your apps (maybe system apps?) and look for “Google Services Framework” and “Google Play Services”. See if you can disable any optimisations and clean the app data. Reboot and then open the Play Store - which might not work well right away - but will force Services Framework to “reload”. Reboot again after a minute or so and see if the problem has improved. I’d also try to remove and re-add your Google account.
One of these (Play Services/Services Framework) handle the “cloud notifications” used for push notifications.