It sounds like an upstream firewall issue. Geo-blocking and SSL inspection will cause issues with app store access.
Can you browse to apple.com from an iOS device?
Does the issue affect MacOS devices as well?
If you found this post helpful, please give it Kudos. If my answer solves your problem, please click Accept as Solution so others can benefit from it.