Real world western european mediaeval, or D&D-flavour pseudomediaeval?
For real world western european mediaeval, subtract potatoes and tomatoes from the menu. They probably cooked a lot with wild onions, wild garlic, and eggs; you could make a fantastic omelette! Also think in terms of religious food rules (fish on Fridays -- although I'm told that a special ordinance from the Pope defined rabbits as "fish" for the purposes of this rule) and figure that as much as possible is preserved, in an era without refrigeration -- hence, for example, salt pork.
For D&D-flavour pseudomediaeval, pick a few D&D critters that taste nice and let your imagination run riot! Frogs' legs are a starter, but giant frogs' legs are a real main course. One roc can feed a village for weeks. Maybe some evil cultures are known to keep pegasi for their eggs, or have a taste for unicorn...
Much more fun than perusing real world mediaeval menus imo.