It's definitely possible. Code like this works:
public boolean onCreateOptionsMenu(Menu menu){
menu.add(0, MENU_PAUSE, 0, "Pause").setIcon(R.drawable.pause);
return true;
}
That creates a menu with one item in it, referred to by the int MENU_PAUSE (a unique identifier number), with the title "Pause" and the icon pause from res/drawable.
If that doesn't do it for you, could you show us your code?
Edit to provide more info based on comments:
It turns out the size of the images matters. The default Android menu images are 48*48 or smaller so it would seem that one must use similar sizes as well. Note: I didn't experiment with different screen sizes, this was only with 320x480 screen.
The alternative is to change the default background of the menu. These can be modified by setting a theme for your application in the manifest and then putting in these lines:
<item name="android:panelBackground">@drawable/yourMenuDrawable</item>
<item name="android:panelFullBackground">@drawable/yourOtherMenuDrawable</item>
The normal menu uses panelFullBackground, so that should be the one you replace first. You can find the default images Android uses in yourSDKfolder/platforms/xxx/data/res/, and they're called menu_background.9.png and menu_background_fill_parent_width.9.png.
I found this information by looking at the default styles and themes files available from the Android source code website