I believe Microsoft Office 97 for Windows was the first time I saw icons next to menu items. Office 97 had highly customizable menus and toolbars. Each menu item and toolbar item could be thought of as an action with an icon and a label, and that action could be placed in either a menu or a toolbar. Not every menu item had an icon associated with it. Additionally, each icon was colored and was clearly distinct.

Office 97 went pretty overboard on customization. It could be awesome if you know what you're doing, but I saw countless examples of where somebody had accidentally changed something and got stuck. Deleted the file menu? tough luck!

This is definitely where I would this pattern - MS Office 97’s customizable toolbars necessitated this model where every single thing you could do in the application had an icon.

It then got copied into Visual Studio, where making all of the thousands of things you could do and put into custom toolbars or menus have visually meaningful icons was clearly an impossible task, but it didn’t stop Microsoft trying.

I assume Adobe, with their toolbar-centric application suite, participated in the same UI cycle.

By the time of Office 2007 Microsoft were backing off the completely customizable toolbar model with their new ‘Ribbon’ model, which was icon-heavy, but much more deliberately so.