It was impossible to get an Icon Package / Theme that would change ALL the icons in the Start Manu. The Typical Problem would arise with the Search and Run icons (I have disabled the rest...)

A small search in the registry and I managed to identify the "keys" that control the default icons.

To change them you need to get in the registry, and that can be done by going to Start > Run (or WinKey+R) and typing "regedit" (yes, without the quotes...)

"Search"
HKEY_CLASSES_ROOT\CLSID\{2559a1f0-21d7-11d4-bdaf-00c04f60b9f0}\DefaultIcon

"Run"
HKEY_CLASSES_ROOT\CLSID\{2559a1f3-21d7-11d4-bdaf-00c04f60b9f0}\DefaultIcon

You can edit each one by double clicking on the respective file.

Hope you enjoy!...

P.S. The easiest way to find the keys, is to go to the CLSID directory, go Edit > Find and search for the name by pasting the {.....} value.