Adding it to the menu will vary slightly depending on what desktop environment you're using, but creating a shortcut on the desktop should be pretty much the same anywhere.
Right click on the desktop and choose "Create Launcher" or "Create Shortcut", whatever your particular file manager says.
You should be presented with a "Create Launcher" popup window. Leave the Type as Application, enter whatever name you see fit, then use "browse" to select the program you've been launching. Optionally you can add a comment, but it isn't mandatory. Also, if an icon isn't selected automatically, you can click on the image towards the left to choose a different icon.
You should also be able to right click on the file you're executing and select "Create link", then cut and paste that link to the desktop. In my experience this doesn't work for all applications/paths, but it works for the most part.
PC: LMDE x64 MATE/Cinnamon, Kernel 3.9, Nvidia GT620, i7 3770K, 16GB RAM
Laptop: LMDE x64 MATE, Kernel 3.8.6, i3, 6GB RAM