I agree with Maya's version. "went" is correct in your context because we moved from where we were standing to another place. If you were already in the kitchen, you could say, "they came into the kitchen". You would say "found" if the discovery was immediate (like "saw") e.g. the remains of the cake were on the table. You would say "found out" if the discovery needed some investigation e.g. you had to ask someone, the cake had been hidden in a cupboard, or you had to some previous work to realise that the kitchen was where the cat had eaten it.

We came into the kitchen and found that the cake had been eaten by a cat. This could be any cat, if you want to say that the cake was eaten by a cat you mentioned before: We came into the kitchen and found that the cake had been eaten by the cat. I would personally say: We went into the kitchen and found that the cake had been eaten by a (or the) cat. I left out "out" from all these sentences, I didn't notice because leaving it out is more natural. It is not wrong if left in.