Play Store error: "Check your connection and try again", tried all possible solutions
I saw that you've all required steps but just check if Google Service Framework is deactivated - normally in the end of the app list or in a tab called "Deactivated" (Settings>Apps>All). Google Framework Services is a must to have in android so that you can update the apps and make connections with Google Servers.

Also reset app preferences (Settings>APPS>(Phone Menu) Reset App Defaults)