В ниспадающее меню,где перечисляются пункты,сепараторы -
слева есть пустое место,где рисуются/не рисуются иконки.
его и надо раскрасить.
Теперь понятно

Боюсь не так просто.

Видимо надо делать свой стиль и свою отрисовку ControlElement для CE_MenuItem, CE_MenuEmptyArea
drawControl(ControlElement element, const QStyleOption *opt, QPainter *p, const QWidget *w = 0) const = 0;
Посмотри исходники "qmenu.cpp" : void QMenu::paintEvent(QPaintEvent *e)