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.