You wouldn't say 'zum Mittagessen gegessen'. It's correct, but the doubling doesn't sound well, so your translation would be better as 'Wir haben Fisch zu Mittag gegessen'. This form is called Perfekt or second past tense and by definition, you use this to state something happened in the past, is finished, but still takes effect in the present. 'Wir haben Fisch zu Mittag gegessen und sind deshalb noch satt' - 'We had fish at lunch and so we're still full'. Here's a big BUT though: This applies only to standard language. It's very common to use the Perfekt as standard past tense instead of the Präteritum in spoken, colloquial, everyday speach. When talking to a german, 'Wir haben Fisch zu Mittag gegessen' would translate to 'We ate fish at lunch'.

This is an interesting peculiarity of German. For meals, you use the preposition "zu." Zum Frühstück means "for breakfast", etc. "Zu Mittag essen" means something like "to eat at noon," therefore "to eat lunch" as opposed to "zum Mittagessen" which means "for lunch." But in both cases, the preposition is a form of "zu."

Wir haben Fisch zu Mittag gegessen. See reply to JoeOcher above