Having same issue with S8 and Tab S3. Also notifications are delayed for random amount of time. Some lag and connection timeouts with different applications, not all though.
Tried factory reset couple times, it fixed the problems for a while but after 1-2 hours they came back. Checked with safe mode if some 3rd party app is causing this. Issues remained in safe mode too.
Got it to work for now by clearing cache and data from Google Framework Services and Google Play Store. Lastly removed and re-added my Google account, rebooted device and wiped cache partition.
Notifications are now on time, Play store starts install instantly.
Still afraid that this is only a temporary fix, waiting to see if these problems arise again after few hours of usage.
Seems there is an issue with Google services on some Samsung devices, mainly running Nougat 7.0