まず AppX Deployment Service (AppXSVC) が依存しているサービス(RPC と State Repository Service)にエラーが出ていないか確認してください。
また AppX Deployment Service (AppXSVC) のスタートアップの種類が「手動」でログオンアカウントが「ローカルシステムアカウント」であることを確認してください。
その上で(これらに問題が無ければ)以下のようなトラブルシューティングを行ってください。
- Windows をクリーンブートする
- サードパーティー製のウイルス対策ソフトウェアを利用している場合はアンインストールする
- Windows に新規ユーザーアカウントを作成して、その新規アカウントでサインインする
- 「システム ファイル チェッカー ツールを使用して不足または破損しているシステム ファイルを修復する」を行う
- Windows を上書き (修復) インストールする