If you start with the elements in $V_{\omega+1}$  and a nonempty set $A$ of urelements, and then simply close under pairing, unions and power sets, you get a model of Zermelo + urelements, but where $A^*$ doesn't exist, even when $A$ is finite, since it doesn't appear after any finitely many applications of pairing, unions and power set (despite your remarks about coding). So you don't avoid the problem by considering urelements, and when there are only finitely many. You still need replacement to prove $A^*$ exists, even when $A$ is finite.