Is it impossible to dynamically instantiate an instance of lightning:menuItem?

Currently no.

The issue is that the body attribute for buttonMenu is of type Aura.ComponentDefRef[] vs the usual Aura.Component[]

Because of that, items passed to v.body are expected to be templates to create components vs actual components.

So you can't dynamically create the menuItem instances.

If you explain more why you want to do that, I could explain some workarounds.

After all this debugging, it appears to be a bug in the framework. Essentially, what's happening is that by the time the menu gets around to rendering the body in changeVisibility, the attribute componentDef on $A.createComponent(s) created lightning:menuItem components happens to be undefined instead of being markup://lightning:menuItem.

This ultimately causes a crash in Aura's $createComponentFromConfig$ method, as it cannot find the definition for this component. The error itself specifically happens on a line that reads something like if(config['descriptor']), which ends up crashing because config is undefined.

Note that I did find you can query the body of an existing menu and manipulate the public attributes of those items, or even remove them from the list. If possible, create a list of as many items as you need in markup, and then use your init method to hide/shuffle/update values as you see fit. I realize it's not ideal, and hopefully this bug will get fixed, but for now, a direct solution appears to be impossible.