Eu não tentei, mas o ShortcutsSearchAndReplace deve fazer o que você precisa. Há uma versão PortableApps aqui também.
Do site:
Shortcuts Search And Replace allows to do easy operations on shortcuts :
- Search for shortcuts target path, working directory, arguments, and icon location content
- Replace multiple shortcuts target path, working directory, arguments, and icon location content (useful when moving portable applications to another drive or another folder)
- Search dead links, to resolve or delete them (multiple resolves/delete in single click)