How can I remove orphaned start menu entries?

You can use the following command to list application icons that link to nonexistent programs:

for i in {/usr,~/.local}/share/applications/*.desktop; do which $(grep -Poh '(?<=Exec=).*?( |$)' $i) > /dev/null || echo $i; done

I suspect you'll find that most of yours are customized icons in your home folder, since these are not automatically cleaned up by the package manager. If this is the case and you'd like to trash them all at once, you can use a modification of the previous command:

for i in ~/.local/share/applications/*.desktop; do which $(grep -Poh '(?<=Exec=).*?( |$)' $i) > /dev/null || trash $i; done

Or, of course, browse to ~/.local/share/applications/ in Nautilus and trash them via the graphical interface.

If by start menu you mean the 'Applications' menu, you can edit it by going to: System -> Preferences -> Main Menu.

You can add, rearrange, edit and delete entries at will.

When an application is uninstalled it should remove menu items it installed. And it work this way on my machine.

If it works differently, it is a bug of a particular package or a problem on your system. I cannot believe that you have more than 40 entry orphaned. It would be the symptom of a problem.