Is this a correct sentence?
Have we a menu?
It sounds a little bit strange to me.
"Have we" is an idiom most familiar to British English, interchangeable with "do we have". It may sound strange to some speakers, but I would not go so far as to call it incorrect, reading the "do" as implied.
It is grammatically correct; however, the style is affected, so it's really not a construction I'd suggest to anyone unless they are native speakers writing something in which an affected tone is useful.