Using Commands in a Shortcut Target

I think the answer is no because a shortcut is not really a symbolic link in the same way it is in linux. The concept of symbolic link was introduced as part of NTFS 5.0, but they apply to directories, not files. Things may have changed in windows 7, I admit to being clueless there. Shell-shocked has a good article on Windows Symbolic and Hard Links.

It would be cool to be proven wrong on this one, because this is a problem I would love to have a solution to at work!

Is there any hex editor in windows that can open lnk file and allow me to edit it?

I don't see why this should be a problem for any hex editor. It might edit the source if you create a symlink or something, but unless the editor specifically has a feature to transparently resolve shortcuts and edit the source, it should work just fine for editing the .LNK itself. I just tried editing both file and dir shortcuts using HxD and had no issues. Of course, if you're looking for a hex editor that actually parses the file and allows you to modify it, you might be out of luck.

There are also command-line programs that you can use to create and modify various aspects of shortcuts, as also Visual Basic scripts.

However, all this is pointless because Windows does not support relative shortcuts in the first place, as can be seen from this Raymond Chen post (be sure to read the associated comments as well).