Uma coisa que posso pensar é escrever um arquivo de lote que altera o diretório de trabalho e executar o programa e, em seguida, inicie esse arquivo em lotes como administrador.
Crie um arquivo runprog.cmd
com este conteúdo e coloque-o em algum lugar:
@echo off
cd C:\some\path
some_program.exe
Em seguida, crie um atalho para ele e mude para o seu ícone. Isso deve funcionar.