I would like to know what's the meaning and in which situations would one use the expression "Enter [somebody]", like "we were trying to find a solution. Enter John".
That's from stage directions written into the scripts for plays. "Enter [Name]" and "Exit [Name]" are commonly used to indicate when a player is entering or leaving the scene.
Naturally, it's been incorporated into the language to achieve a dramatic effect, and has come to be used when the speaker or writer wants to achieve a bold announcement, especially in titles. Cf. Enter the Dragon, Enter Sandman, etc.
In the example you gave, the phrase Enter John, is another way of saying "this is where John comes in (to the story)." It also implies that John was the solution to the problem, or that he figured out the solution. So Enter [somebody] (stage direction shorthand as mentioned) is often used in conversation to indicate coincidental, surprising, or opportune timing.