If you only one program then you have to use that, but depending upon the nature of the design of your menu any of the standard programs mentioned will do the job.
I'm an Illustrator user for packaging graphics/identity/logos and often use it for posters, stationery etc. as I like having 'live' vector illustrations on the page rather than an imported EPS or JPEG file.
Other times a layout job that has pages will always be set in Quark or if requested in InDesign. I'm a bit old school and do 90% in Quark. The part the printer gets is the PDF so it's not really an issue which application is used unless the printer wants to work from the native file.
If your design has multiple elements (text, images: photography or illustration) and possibly logos from brand names (Coca Cola, Fairtrade Coffee etc.) then you may err on the side of a page layout program to create the front, back and internal pages. Illustrator could easily handle this too, but it's a preference thing.
You'd never layout a brochure or a magazine in Illustrator.