Are still using an MS account or local?. Try logging out and in again a couple of times with the local account. If an MS account, log in to
https://login.live.com and ensure your account is still up to date.
On a temporary attempt, create a new account and log in. See if you can then access the store.
Only other, more drastic, measure I can think of is a complete refresh.
The obvious: You have checked that your OS is still activated. For various reasons, it can become inactivated. I presume the Windows 8 installation came with the computer. Sorry for the intrusion, but was this a retail or private purchase? Things can be doubtful with the latter. I guess, also, you installed Windows 8.1 with one of the known bypass methods...