The application has to come with a .desktop file, normally installed under /usr/share/applications (open some of those .desktop files with a text editor as an example). Properly packaged debs should include that (along with other stuff like man pages, documentation, etc., all installed in the right directories). If not, create your own .desktop file and place it in ~/.local/share/applications.
"Edit Menu" calls /usr/bin/alacarte...but alacarte is probably Gnome-specific. Well, mintMenu was designed with Gnome first and foremost, after all.
Debian Testing x64/LM9 Main x64/Windows 7 x64 - LG R580 laptop w/ Intel Core 2 Duo T6500 2.1 GHz, 4 GB DDR2 RAM, Nvidia Geforce G 105M, Ralink rt2860 802.11n, 300 GB WD HD 5400 rpm