Para a modificação em lote de arquivos de atalho, você pode experimentar este software: Pesquisa e substituição de atalhos (está disponível até como um aplicativo portátil ).
Detalhes:
Eles o instalariam (já que há uma versão portátil que não deve ser muito complicada para o sistema operacional) e a usam para alterar as propriedades de seus atalhos.
Eles podem especificar caminhos personalizados onde procurar atalhos, bem como caminhos padrão, como a pasta da área de trabalho, como você mencionou, o menu iniciar um e assim por diante.
Então, este é um mecanismo básico de pesquisa / substituição com dois campos de texto, para que você possa fornecer os padrões para inserir (como na descrição da sua pergunta).
Depois, eles podem iniciar a pesquisa, visualizar o resultado e aplicar as modificações ou não.
O fato de fazê-los usar um software para aplicar manualmente as modificações provavelmente não é a melhor prática, entretanto esta é a solução mais rápida que eu tenho em mente, e isso é bastante robusto, pois lidaria com qualquer configuração personalizada que eles pudessem ter ( caminhos personalizados e nomes para seus atalhos, basicamente). Além disso, para isso ou não, isso é, na minha opinião, uma utilidade útil para manter à mão.