What is a paradox...
My answer to your question is mainly not related to physics or cosmology, but to the question what a paradox actually is.
If you think back to several other paradoxes, you see that a paradox can be several different types of arguments. For example, mathematical proofs that end up with $1=2$ may be called paradoxes, and they simply hide the error very well from the casual reader. Paradoxes like Zeno's Turtle are not themselves based on errors, but show up areas of research/knowledge that are simply missing (here: infinite sums), and where applying conventional wisdom just leads to wrong results. Theseus' Ship contains no error at all, and just makes use of unclear definition of seemingly simple words (here: "same").
Relation to Olber's
So. Asking "what is the paradox in Xyz" assumes that there is some particular "weirdness" going on, or that there is one specific bit in the argument that makes it a paradox, but this does not need to be the case. In Olber's Paradox, the problem was simply that the assumptions (infinite size, homogenous distribution, static (i.e., unmoving, undying) stars) lead to a result which differs from what we see each night. It is a simple Reductio Ad Absurdum, and the term "paradox" here simply means that the result (that the universe cannot be infinitely large) was very unexpected or surprising at the time.
Back then, it was not obvious to everybody that you could challenge whether the infinity or static properties of the universe are really true; hence the grand word "paradox". There could have been the possibility that, as in Zeno's Turtle, all the assumptions would have been actually true, and there was just an additional bit of knowledge in addition that we were missing (which did not turn out to be the case).
You do not need infinite time, so it is reconcilable with christian creation. This is because at that time people did not really know for sure that light moves at finite speed. They had no concept of event horizons and the like. They did not know that stars are born or can die (Thomas Digges interpreted a supernova as a star moving closer and thus starting to be visible). There were strong supporters of "infinite+static", i.e. Digges, Bruno, Galilei.