If a machine is blocking built-in applications, why would it have MSPaint available? Or is it an application that cannot be blocked, which would be a security vulnerability?
I spent 10 years doing corporate desktop deployments of Windows. You'd be surprised at the crazy requests from the business regarding what they did and didn't want pre-installed.
Also, GPOs can (and do) disable the Windows Store. So moving MSPaint to the Windows Store does not make as available as having it pre-installed.