Which one is correct?
He looked up at the sky and found that night ___.
 fell  had fallen  has fallen
It would depend on the context.
If you are describing the event as it happened, you could say "he looked up and (as he did so, he) found that night fell".
If you are describing the realisation of event that had already happened, you would say "he looked up and found that night had fallen".
I cannot currently find a situation where "found" and "has fallen" can be combined. You could say "if you look up, you will find that night has fallen".
 He looked up at the sky and found that night had fallen.
The sentence is in past tense, describing the actions of the subject at one point in time. Night fell before he looked up, so you would use past perfect to describe an action that was completed before the narrative time frame.
Simple past tense (1) would be used to describe a contemporaneous event, as something that happened at the same time, but in that case you would not say he "found" it (rather, "He looked up and night fell.").
Present tense (3) is used to describe something happening now, which does not agree with the rest of the sentence which is in past tense.