If there's a time at which the stars are born, then there's no paradox. Non-star things can stay cold for the same reason comets stay cold in our universe: they can radiate heat in almost all directions (into the black sky) and receive heat from only a few (like the sun on a brief swingpast, still only < 1% of the sky).

But if the stars have been there forever, the comet is effectively in an oven of uniform temperature. The equilibrium state at which it radiates heat as fast as it gets it has the comet's surface the same temperature as the rest of the oven. So it glows.