There was talk in past years about the Matroska (MKV) video container format using menus, but I don't think it ever happened. In other words, it's a vaporware feature -- it never existed beyond some research and trials.
The only way to both have a menu AND keep HD resolution is to create a Blu-ray disc, or to create a BD-on-DVD disc. That's where you use put high definition H.264 on a DVD. But then again, I don't think you can easily make BD menus.
There are several sub-formats of Blu-ray, each with its own authoring specs, and at least one of them is menu-less. I've not had time to really get into it, mostly because customers don't ask for Blu-ray work -- and that includes corporate and small/medium studio work.
I think you'd be best off just encoding it as a 720x480 DVD, and make menus that way.
Or skip the menus and leave it as a MKV on the computer.
Or create a BD-on-DVD disc with no menu.
Or a combination of two (or all three) of the above suggestions.
Blu-ray is, at its core, a Sony proprietary format. And those are NEVER easy to work with. They've more or less created an expensive and complex format -- even more than DVD was in it's earliest stages.
Post back the solution you choose!