One way to accomplish this is to create an NSPopupButtonCell subclass and draw the text yourself in its drawTitle:withFrame:inView: method.
Here's the essence of it:
@interface MyCell : NSPopUpButtonCell
    @property NSDictionary<NSString*,id> *attrs;
@end
@implementation MyCell
-(NSRect)drawTitle:(NSAttributedString *)title withFrame:(NSRect)frame inView:(NSView *)controlView
{
    CGSize cs = controlView.bounds.size;
    CGPoint or = frame.origin;
    CGSize fs = frame.size;
    const int th = fs.height;
    const int inset = th * 2 / 3;
    const int indent = self.image ? th+6 : 0; // assuming the img is on the left of the text, we'll indent the text
    frame = CGRectMake (inset+indent, or.y, cs.width-2*inset-indent, fs.height);
    return [super drawTitle:title withFrame:frame inView:controlView];
}
@end
Note: This code does not cover all possible cases of adding an icon to the menu items - it only handles the most common case of having a fitting icon on the left, and that's still a bit wonky because of using indenting values I found by trial-and-error. Adjust them yourself as needed.
See also the comment below by @NSGod about setting up the cell's class in your nib or storyboard.
Update: Optimized the code to need only a subclass of the NSPopUpButtonCell but not of NSPopUpButton, thanks to @NSGod.
Update 2: Instead of implementing drawTitleWithFrame:inView: I now overwrite drawTitle:withFrame:inView: because that gives me the correctly centered frame for drawing and makes the whole code shorter.