Problem
Windows store is not accessible from the start menu and any where. This may occur randomly or after a profile rebuild.
Solution
Re-Registed all the apps by running this powershell command in an elevated PowerShell console.
Get-AppXPackage | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)AppXManifest.xml"}