PowerShellでのアンインストールを試されたとのことですが、Microsoft Store自体の再インストールは含まれていましたか？ もしまだであれば、以下の手順でMicrosoft Storeを再デプロイしてみてください。
タスクバーで「Windows PowerShell」を検索し、右クリックして「管理者として実行」を選択後、以下のコマンドを実行します：
get-appxpackage *store* | remove-appxpackage
その後、こちらのコマンドで再インストールします：
add-appxpackage -register “C:\Program Files\WindowsApps\*Store*\AppxManifest.xml” -disabledevelopmentmode
もし最初のコマンドが機能しない場合は、直接2番目のコマンドを試してください。または、以下のコマンドも有効な場合があります：
Get-AppXPackage *Microsoft.WindowsStore* | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register “$($_.InstallLocation)\AppXManifest.xml”}
これでStoreが正常に使えるか確認してください。
それでも解決しない場合、アカウントのプロファイルに問題がある可能性を切り分けるため、新しいローカル管理者アカウントを作成し、そちらで同様の問題が発生するか確認してください。Windows でユーザー アカウントを管理する - Microsoft サポート
上記のいずれの方法でも解決しない場合は、インプレースアップグレードによるシステムの修復が必要になる可能性が高いです。免責事項：インプレースアップグレードは個人用ファイルやアプリを保持したままシステムを更新しますが、万が一に備え、重要なデータは事前にバックアップすることをお勧めします。Windows 10 を上書き (インプレース) アップグレードする方法 - Microsoft コミュニティ