You need to subclass NSPopUpButton and NSPopUpButtonCell, which manages the drawing. Look at the three drawing methods used in NSButtonCell for what you need to override (or just the generic NSCell one).
If you're trying to customize the actual menu items that show, there's not a lot you can do other than providing your own view and doing all the drawing yourself.