最近の Office のプリインストール環境は UWP 版 Office（ストアアプリ）がインストールされているケースがあるようです。
UWP 版 Office は COM の公開方法が Desktop Bridge 向けの新しい仕組みが採用されています。
COM Server and OLE Document support for the Desktop Bridge
https://blogs.windows.com/buildingapps/2017/04/13/com-server-ole-document-support-desktop-bridge/
このため、レジストリから Excel.Application を探しても見つからないが、COM オブジェクトは生成できるという不思議な状態になっています。
興味のある方は上記の記事を参照しつつ、UWP 版 Office のインストール先の AppxManifest.xml を覗いてみましょう。
なお、今のところ、管理者権限で実行したプロセスからは Excel.Application といった ProgID から COM オブジェクトを生成できないようです。
これが仕様による制限なのか、不具合なのかは不詳です。
CLSID を直接指定すると生成できるという情報（MSDN フォーラム）もありますので、必要な方はそちらも検討してください。
管理者権限で Excel をオートメーションで利用されている方は以下のいずれかになります。
- 管理者権限で実行しないで済むように運用や設計を見直す
- UWP 版 Office をアンインストールして、従来のデスクトップ版 Office をインストールし直す
Microsoft ストア アプリ版 Office 2016 から、デスクトップ アプリ版 Office 2016 に入れ替えることはできますか。
はい。Microsoft ストア アプリ版 Office 2016 をアンインストール後、マイアカウント ページからデスクトップ アプリ版 Office 2016をインストールすることができます。
（https://www.microsoft.com/ja-jp/office/setup/2016pipc/faq.aspx より）