"Check Your Connection And Try Again" repeated toasts
Based on your assertion that your issue is not Play Store-related, I believe it is a malfunctioning app.

The Toaster app will help you track down the source of these "toast " notifications.

The app description reads:


  Records every toast message including the sender package. May be helpful if you get messages and don't know which app sends it.


Update: As confirmed by OP, the Toaster app worked and the app responsible for the repeated notifications (as determined by Toaster) is NYTVR, the VR app of New York Times. Interestingly, there is one  user review there which complains of the same problem faced by you!

Update 2: I tried downloading the NYTVR app to see if the same problem would arise (I am also on same OS, though I have a Moto X Play); however, I did not encounter any such notifications, which makes me think that this may not be purely OS-related, but rather a general bug in the NYTVR app that only occurs on certain devices. 



If Toaster indicates that a certain app is sending the notification, make sure that app is updated and has settings set in a standard way. If you can't stop the notifications, contact the developer of the app or uninstall it.

Hope this helps!