It's clear that the axiom of replacement can be used to construct very large sets, such as $$ \bigcup_{i=0}^\infty P^i N, $$ where $N$ is the natural numbers. I assume that it can be used to construct sets much lower in the Zermelo hierarchy, such as sets of natural numbers, but I don't know of an example. Is there an easy example? (Just to be clear, I mean an example that requires the use of replacement, not just one where you could use replacement if you wanted to.)

I would guess you can cook up an example using Borel determinacy, since that involves games of length $\omega$, but it would be great if there was an even more direct example.

Also, I'd be curious to know for any such examples at what stage they first come along in the constructible universe. $\omega + 1$? The first Church-Kleene ordinal? Some other ordinal I've never heard of?

a certain set, you can't (at least, not naïvely) mean “an actual set in a particular model”, since either that model believes replacement or it doesn't. On the other hand, if we instead mean “some formula defining a set”, we run into the issue Ricky points out. – Peter LeFanu Lumsdaine Oct 15 '10 at 23:24