Olbers' Paradox applies to a universe that is infinite and unchanging in both time and space. In such a universe, no matter where you looked, in every direction there would eventually be a star. Thus everything would be the same temperature as the surface of a star.
You can solve this paradox in three ways:
1. Allow the universe to be finite in time. In such a universe, light wouldn't have had time to come from every location in the universe yet, as you mention.
2. Allow the universe to be finite in space. In such a universe, obviously not all directions would necessarily point to some star or other, since there would be a finite number of them.
3. Allow the universe to expand with time. In such a universe, the light from further-away stars is redshifted more, such that the temperature of the night sky is only affected by the most nearby stars, which are also finite in number.