I have an App Store update indicated on my App store icon, but when I click on it to go to the App store I get the message >Cannot Connect to App Store
There are two places you need to check, both under "Settings": "Mobile" and "App Store." Under "Mobile", find Use mobile data for: and scroll down until you find App Store. Make sure the switch is toggled to green. Next, go back to Settings and scroll down until you see "iTunes & App Store." Click on that and make sure "Use mobile data" is toggled to green.
If you are in the US or another region, "Mobile" may be labelled "Cellular" and "Use mobile data" may be "Use cellular data"
Here are two screen shots to help direct you: