"NeXTStep had its Dock, but that doesn't have menus or a status icon."
NeXTStep not only had menus but tear-off dockable menus/sub-menus that are superior to any menus we have in apps today. It's clearly present in the screenshot I linked to.
https://youtu.be/rf5o5liZxnA?feature=shared&t=542 has a demonstration of NextStep 3 (released September 1992) that clearly shows a computer icon that Steve refers to as "My Computer" and then moves into hitting the "Network" icon globe that shows other computers on his local network.
NeXTStep not only had menus but tear-off dockable menus/sub-menus that are superior to any menus we have in apps today. It's clearly present in the screenshot I linked to.