Either of those programs, except DvdReMake, can easily create the menu from scratch. Whichever one you feel comfortable using. But a whole new DVD must be created because a menu is created and the IFOs are changed.
About the shortcut, when you use either of these programs, you can just import a very short clip instead of the real big titleset. The whole purpose is so you can export quickly because all you want is the menu. Then you can import the created menu into DvdReMake, and replace each short clip with the real titleset, making sure you have the right video/audio/subtitle attributes set and enabled, and probably defining the chapters. If you're not comfortable with this approach, then don't use it. Then forget the shortcut I mentioned and you don't need DvdRemake in the process.
Use the real titlesets instead for these mentioned programs. A whole new DVD will be recompiled. It doesn't take long anyway if you are using 2 HD. You might want to look at DVDStyler, GUI for DVDAuthor, and DVDLab to see which one you like. I think TDA and NVE re-transcode the titlesets.
There's another free program, Titlewriter, to create simple menus without doing the whole reauthoring that you might want to take a look.