Remove the app, repair Windows Store, profit. Thanks to zax for this solution. Here is the cmdlet to remove an app for all users:
$appToFix = "*media*" # As an example
Get-AppxPackage -Name "$appToFix" -AllUsers | Remove-AppxPackage -AllUsers
If you want to ensure the application is the latest version for all users, you can run this cmdlet:
$appToFix = "*media*" # As an example
Get-AppxPackage -Name "$appToFix" -AllUsers | Sort-Object -Descending -Property Version | ForEach-Object {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml" -ForceTargetApplicationShutdown -Confirm }