The replacement axiom (axiom scheme) is the most general form you need, essentially saying that if you have a function whose domain is a set then the image is also a set. Furthermore, the empty set can be inferred by an existence of any set at all, when combined with separation (and hence, can be inferred by replacement).
Formally speaking the replacement schema says that for every formula $\varphi(u,v,p_1,\ldots,p_n)$, fix the parameters $p_1,\ldots,p_n$ and pick any set $A$, whenever $u\in A$ has at most one $v$ for which $\varphi(u,v,p_1,\ldots,p_n)$ is true, then the collection of $\{v\mid\varphi(u,v,p_1,\ldots,p_n), u\in A\}$ is also a set.
How to infer separation and pairing? Simple.
First we infer separation. Given $\phi(x)$, we simply define $\varphi(u,v,p)$ to be $$\varphi(u,v,p)\stackrel{\text{def}}{=} u=v\land u\in p\land\phi(u)$$
This is a functional formula (i.e. for every $u$ there is at most a single $v$ for which $\varphi(u,v,p)$ holds) and it is easy to verify that the image of $\varphi(u,v,a)$ is indeed $\{x\in a\mid \phi(x)\}$.
The empty set exists by separation - simply take some $a$ (which exists because we assume there is some set in the universe) and the function $\phi(x)\colon = x\neq x$.
As you noted, $\{\emptyset ,P(\emptyset)\}$ exists by the Power set axiom.
Now for a given $x,y$ we want to have $\{x,y\}$ so we define the following $\varphi(u,v)$ as following:
$$\varphi(u,v) \colon = (u=\emptyset\wedge v=x)\vee (u=P(\emptyset)\wedge v=y)$$
Note that $\varphi$ is a functional formula, i.e. for a given $u$ there is only one $v$ for which $\varphi(u,v)$ is true. By the axiom of replacement we have now that $\{x,y\}$ is a set. Therefore the axiom of pairing holds if we assume Power set and Replacement.
Now we have two ways of looking at ZFC. Sometimes we want to prove that something is a model for ZFC and need to verify the list of axioms in which case proving both Separation and Replacement is completely redundant. At other times we want to prove certain things which are quicker when using the more specific axioms (e.g. pairing (or even ordered pairing, which can be quickly inferred from pairing itself)).
This is a sort of freedom that we allow ourselves. We add extra axioms that we don't really need. Then if we want to ensure all the axioms hold we check for the "core" of the axiomatic system, and when we want to ease on ourselves in other cases we can just use the extra axioms for our convenience.
You have $x,y$, let us construct the pair $\{x,y\}$.
First note that $\varnothing=\{z\in x\mid z\neq z\}$. So we have the empty set. Now by the power set axiom we have $P(\varnothing)=\{\varnothing\}$ and $P(P(\varnothing))=\{\varnothing,\{\varnothing\}\}$.
Now let us define a formula (with parameters $x,y$):
$$\varphi(u,v,x,y)\colon= (u=\varnothing\land v=x)\lor(u=\{\varnothing\}\land v=y\})$$
(Note that $\{\varnothing\}$ can be defined explicitly as the set that all its elements are the empty sets)
Using replacement now, we set the parameters $x,y$ now the axiom says that $\{u\mid\exists v\in P(P(\varnothing))\colon\varphi(v,u,x,y)\}$ exists. But this set is exactly $\{x,y\}$.
You cannot use the axiom of union to prove from the existence of $\{x\}$ and $\{y\}$ the existence of the set $\{x,y\}$. The axiom of union says that if $A$ is a set then $\bigcup A$ is a set. However you want to say that $\{\{x\},\{y\}\}$ is a set therefore its union, which is $\{x,y\}$ is a set. You already assume the existence of a pair.
You can indeed use separation to prove the existence of $\{x\}$ using the power set axiom as well.
To use a power set, or separation argument you have already the existence of some set. Note that the power set axiom says that if $x$ is a set then there exists a set which contains all the subsets of $x$. Separation is the same, you assume the existence of a set. If you wish to use these two, adding an assumption that an empty set exists is meaningless (note that empty sets exists due to separation, so using it for $\{x\}$ is the same as using it for $\varnothing$).
Best Answer
Definition. Let $x$ and $y$ be sets. The ordered pair $x$ comma $y$, denoted $(x,y)$, is $\rule{50pt}{0.4pt}$.
Here $\rule{50pt}{0.4pt}$ represents any definition used.
Remark. Let $x$, $y$, $u$, $v$ be sets. Then $(x,y)=(u,v)$ if and only if $x=u$ and $y=v$.
Here it is assumed that the above remark can be proven, and is the assumption $\color{blue}{(*)}$ you mention.
Proposition. Let $R$ be a set. Then $\{x:(\exists y)[(x,y)\in R]\}$ is a set.
Proof. Define the formula $\varphi$ with free variables $\check{p}$ and $\check{x}$ by $$\varphi(\check{p},\check{x}):=(\exists y)[(\check{x},y)=\check{p}].$$ By the axiom of replacement, $\{x:(\exists p\in A)[\varphi(p,x)]\}$ is a set. Indeed, $$\varphi:p\mapsto x$$ satisfies $(\forall a)[a\in A\:\Rightarrow\:(\exists!b)[\varphi(a,b)]]$ by $\color{blue}{(*)}$. That is to say $\varphi$ is a class function. Here $A=\{z\in R:(\exists a)(\exists b)[z=(a,b)]\}$.
$\square$
This proposition and proof can be modified to prove the range is a set as well.