If I'm reading you correctly you are saying:
1. The actual executable files for the programs you are trying to run were resident on an external hard drive that no longer exists.
2. Said programs were "portable"/stand-alone type, that is, you didn't run an install process but could copy the .exe file where you wanted it and run it.
If that's the case, and the only location where you had copies of those programs are on that now defunct external drive, and the shortcuts were created such that they point to a location on that now defunct external drive, there is no way to eliminate the message. It's accurate, a valid path to the file, which is a part of the shortcut, no longer exists.
If you copied some of these executables over to any other drive that's still alive you should simply delete the existing shortcuts from your desktop and create new ones from the executable files where they reside now.