First of all, the KMenu icons can be found under the name start-here-kde.png and are located by default in the following directories (for the Oxygen theme):
$ find /usr -name *start-here-kde*
If you have some other theme selected, replace oxygen with it. Next, download a set of KMenu icons, for example you can try with this one from kde-look.org.
Then, replace all the start-here-kde.png icons inside those directories I mentioned above.
Next, open System Settings, go to Appearance and select the Icons tab. Change the icon theme to something else, then change it back. The KMenu should be now replaced.
Change the theme to something else, then switch it back so the changes to KMenu will be visible
Here's how the KMenu looks now:
Mandriva KMenu in KDE 4.2