そのフォルダー内の「.exe」ファイルはひとつだけでしょうか、他にもあればそちらでも試してみてください。
また、PC
には管理者権限のあるユーザーでログインしているのでしょうか、そうでなければ管理者権限のあるユーザーでログインしてください。
その状態で作成したショートカットを右クリックして「プロパティ」を選択し、「ショートカット」タブの詳細設定をクリックして出てくる画面で、「管理者として実行」にチェックを入れてみてください。
スタートメニューにあるプログラムについても同じように設定できないでしょうか。

改善されない場合は、クリーンブートやセーフモードで起動してみて、ショートカットが起動するかどうか確認してみてください。
それで起動すればセキュリティソフトなど他のアプリが起動を阻害しているのかもしれません。
なお、セーフモードはメーカーにより起動方法が異なる場合もあるので、その場合はネットで調べる、説明書をみる、メーカーに聞くなどして確認してください。
クリーンブート:常駐アプリケーションを解除する方法
セーフモードで起動する方法
【Program Files】フォルダー内にある「.exe」ファイルを直接ダブルクリックしても起動しないのでしょうか。
コマンドを使えるのであれば、次の方法でも試してみてください。
スタートメニューのアクセサリーからコマンドプロンプトを右クリックして、「管理者として実行」で起動してから、実行ファイルを直接指定して起動するかどうか確認する。
例:Cドライブの「Program
Files」フォルダーにある「7-Zip」フォルダーの中の実行ファイル「7zFM.exe」を起動させる場合:(□は半角スペースです)
〔cd□/d□C:\Program
Files 〕で「Program Files」フォルダーに移動する
〔7-Zip\7zFM.exe
〕で「7-Zip」フォルダーの中の実行ファイルを指定して起動する
これらで改善されない場合は、そのアプリをアンインストールしてから再インストールして改善されないでしょうか。
あるいは、
≪このソフトウェアの説明文では、このインジケータ内の小さなこのソフトウェアのアイコンを左ダブルクリックして実行するよう示されています。≫
ということであれば、実行ファイルからは起動できないアプリということなのかもしれません。
インストール時にスタートメニューに登録されるのに、そこから起動できないというアプリがあるのかどうかは疑問なのですが、ネットで調べてみるとか可能であればそのアプリの作者に連絡して聞いてみるということはできないのでしょうか。
また、的外れかもしれませんが、
起動時からすでに常駐していて、実行ファイルからは起動させないような仕組みなのかもしれません。
ダメもとで、常駐の有無を上でリンクした「クリーンブート」と同じ方法=システム構成ユーティリティを開いて、「スタートアップ」や「サービス」に該当するものがあれば、チェックを外してみるという方法を試してみてもいいかもしれません。
また、どのようなアプリなのか、どこにインストールされているのかなどを具体的に書けば、ひょっとしたら他の人からもアドバイスが得られるかもしれません。