Os arquivos de links realmente suportam caminhos relativos. Consulte esta pergunta no Stack Overflow para mais detalhes. Há também alguns truques que você pode usar, como criar um link para o cmd.exe, que sempre será executado e, em seguida, iniciar o executável a partir do diretório atual.