Icons are for items you need to find at a glance. You really want to prioritize those commands I'll be using all the time, the ones I'll need quickly with one click. Once I've learned what the icon is I don't have to read; I can immediately identify icons even in my peripheral vision.
A thing about icons in menus like this; generally they're for power users. They're not always recognizable when you first use an app; some things are just too abstract for a tiny little 16x16 icon. But once you've got to learn that the plus and the chart means "Connect to Team Project" you can immediately pick that one and go, even if it wasn't intuitive when you first saw it.
Note some of those commands have icons because they're presented in a toolbar (possibly without a label). Consistency (even if redundant) is key here. Why have the Toolbar save button have an icon but the Menu save command doesn't have an icon? Are they really different commands?
Clarify is also important. Note that Save As doesn't have it's own icon. Sure, it's not as common as Save, but a bigger reason not to give it an icon is the most logical icon is too similar to Save. When you have similar commands that can't be given distinct commands, instead give one of them an icon and group them together logically. I can still see the floppy disc icon and recognize "Oh, Save As is right in that same section, between the dividers"; with good IA and applying Gestalt Psychology principles you can group functionality together without the need for too many icons.
An interesting thing to note is in the first example, Microsoft is clearly using a convention where nested menus don't have icons. That makes some sense; icons are for functions (not always; but it's a local convention they're using here). Sometimes you have to make your own conventions.
Now an issue I note in your design is there's an icon for Done. Why? It's in it's own corner with a clear label, nothing to miss click on, it's easily identifiable via peripheral vision. If a button is clearly identified already, icons are probably overkill. You don't often see Submit buttons with icons because they're generally designed to stand out enough as it is.
Also note there's a point when there are just too many icons; the first example is Visual Studio which has a lot of menu items. Even power users can have trouble picking out dozens of app-specific icons, so don't over-do it. Your menus are small enough (from what I see here) that you're not close to overdosing on icons. Yet.