Given sets $A$ and $Y$, I want to show that there is a set $T$ such that given $a\in A$ an $y\in Y$ the ordered pair $(a,y)$ belongs to $T$.
$$$$
In other words we want to show that the existence of the set of ordered pairs $A\times Y$, or not?
For that do we have to apply the axioms of sets?
Assuming that the ordered pair $(a,y)$ is defined via the Kuratowski definition, $$(a,y) = \Bigl\{ \{a\}, \{a,y\}\Bigr\}$$ and that you are working with ZF theory, this is relatively straightforward.
By the Axiom of Pairs, there is a set $X=\{A,Y\}$. By the Axiom of Unions, there is a set $B=\bigcup X = \{x\mid x\in A\text{ or }x\in Y\}$. In particular, if $a\in A$ and $y\in Y$, then $a,y\in B$. By the Axiom of Separation, $\{a\}$ and $\{a,y\}$ are sets, $\{a\}\subseteq B$ and $\{a,y\}\subseteq B$.
By the Axiom of the Power Set, $\{a\}$ and $\{a,y\}$ are elements of $P(B)$, the power set of $B$. Therefore, by the Axiom of Separation, $\{ \{a\},\{a,y\}\}$ is a set, and since it is a subset of $P(B)$, hence by the Axiom of the Power Set, $(a,b)$ is an element of $P(P(B))$.
By the Axiom of separation, $\{ x\in P(P(B))\mid \text{there exists }a\in A,y\in Y\text{ such that }x=(a,y)\}$ is a set. This is exactly the set $A\times Y$.
(Note: There is a subtle issue with Separation above in that the formula has two free variables, but this can be solved using the Axiom of Replacement)
If you have a different definition of the pair, then similar arguments can be made, though the precise sequence of axioms and operations may differ.
Note: the Axiom of Choice is not required. This party can happen in ZF.