I have been suffering from this problem for a few days now.  Some of my apps won’t even open due to the lack of connectivity with the App Store.  After doing the basic googling I found this support article from Apple.  https://support.apple.com/en-us/HT203811

OS X: “Cannot connect” or “Cannot connect to the App Store. An internet connection is required”

While attempting to use the Mac App Store on your Mac, you may see the message, “Cannot connect to the app store. An internet connection is required.” There are a few different situations that can cause this message to appear. Please consider each of the following situations and their potential resolutions.

So I worked through the individual steps and rebooted after each one.  After trying the steps to remove Invalid or Incorrect Certificates I got the following error:

I knew I was onto the right track.

I then followed the steps to edit the certificates in the KeyChain App, however some of the steps were not showing what I was seeing on my system.

These are the steps Apple tell you to complete:

1. Open Keychain Access located in /Applications/Utilities/
2. Select Certificates from the left hand column under Category
3. Type Class into the search field in the top right corner of the Keychain Access window and press return.
4. Look through the list of results for any certificates that have a blue + over the icon.
5. Double-click on a certificate that has the blue + over the icon to ‘Get info’ on the certificate.
6. Click the disclosure triangle to the left of the word Trust to reveal the certificates permissions.
7. Change Secure Sockets Layer (SSL): to ‘No Value Specified’ then close the window.
8. Confirm the Administrator password in the window that will appear.
9. Double-click on the same certificate that was opened in step 5.
10. Again Click the disclosure triangle to the left of the word Trust to reveal the certificates permissions.
11. Change When using this certificate: to ‘Use System Defaults’ then close the window.
12. Again confirm the Administrator password in the window that will appear.
13. Repeat steps 5 through 12 for any certificates that have a blue + over the icon. (Generally there are only one or two that will need to be edited.)
14. Restart the system and test for the issue.

Step 4 and 5 talk about looking for Certificates with Blue + Icons.  I could not see any certificates with Blue + Icons, however I could see certificates that had blue icons.  I opened up any of the certificates with a KeyChain Type of Login and followed the steps listed above.  All the certificates already had the settings described.  I decided to change the settings to custom and to always trust the SSL Connection (maybe not the most secure, but worth a try anyway).

I changed three certificates to this, and re-booted the system.

Upon re-boot I opened up the App Store App and it works!

What I also found when I checked the certificates again was that they had the Blue + Icon showing now.

Give it a try, hope it solves the problem for you.