Is every subset of a set a set?
1) Yes using the Comprehension Scheme you can define $A\times B$ as the set $$A \times B := \left\{ x \in \mathcal{P}(\mathcal{P}(A \cup B)) \ \mid \ \psi[x,A,B] \right\} $$ where $\psi[x,A,B]$ is the formula $$ \exists a \exists b (a \in A \land a \in B \land x = \left\{\left\{a,b\right\},\left\{b\right\}\right\}) $$ Firstly you know that the set $\mathcal{P}(\mathcal{P}(A \cup B))$ exists after you've constructed it using the Powerset axiom and you know that this set containns all the ordered pairs. Then the Comprehension Axiom Scheme asserts that all the things that can be extracted from existing sets with first order formulas are sets that exist as well. With that you can assert that the constructed set $A\times B$ exists and it has the right properties that you want containing only the ordered pairs because of the way you've constructed it. There is no need to mention "subset" anywhere. In fact subset notation $X \subseteq Y$ is just abbreviation for the formula $\phi[X,Y]$
$$ \forall a (a \in X \implies a \in Y) $$
2) In order to say something is a subset of a set it has to be set in the first place. $ZF$ works only with sets and nothing else. If something is "not a set" there is no way to even refer to it in $ZF$ because the first order formulas of the meta-language quantify only over sets. This means that even if we ignore the Power Set axiom with which you can show that all subsets of an existing set are sets that exist, we cannot express the statement that there exist a subset of a set that is "not a set".
Let $A,B$ be sets.
Then by Pair there exists a set $C$ with $\forall x\colon x\in C\leftrightarrow x=A\lor x=B$. (The Pairing axiom can be expelled by using Infinity and Power and Replacement, but I like to use it for convenience).
Then by Union, there exists a set $D$ with $\forall x\colon x\in D\leftrightarrow\exists y\colon x\in y\land y\in C$.
Then by Power, there exists a set $E$ with $\forall x\colon x\in E\leftrightarrow\forall y\colon y\in x\to y\in D$.
Then by Power, there exists a set $F$ with $\forall x\colon x\in F\leftrightarrow\forall y\colon y\in x\to y\in E$.
Then by Comprehension, there exists a set $G$ with $$\begin{align}\forall x\colon x\in G\leftrightarrow {}&{}x\in F\\&\land\exists a\exists b\exists u\exists v\forall t\colon\\ &\qquad\ a\in A\\ &\quad\land\ b\in B\\ &\quad\land\ t\in u\leftrightarrow t=a\\ &\quad\land\ t\in v\leftrightarrow (t=a\lor t=b)\\ &\quad\land\ t\in x\leftrightarrow (t=u\lor t=v)\end{align}$$ is a set by Comprehension.
About $G$, we readily prove that each of its elements is a Kuratowski pair of an element of $A$ and an element of $B$ (in fact, the convoluted formula states precisely what could be abbreviated as $x=\{\{a\},\{a,b\}\}$)
On the other hand, let $x=\{\{a\},\{a,b\}\}$ be a Kuratowski pair of an element of $A$ and an element of $B$. We directly find that $A\in C$, hence $a\in D$. Likewise $B\in C$ and $b\in D$. By Pair, the set we write down as $\{a\}$ (i.e., a set $X$ with $\forall z\colon z\in X\leftrightarrow z=a$) exists. As $a\in D$, we conclude $\{a\}\in E$. Similarly, we conclude that $\{a,b\}\in E$ from $a\in D$ and $b\in D$. Similarly, we conclude that $\{\{a\},\{a,b\}\}\in F$ from $\{a\}\in E$ and $\{a,b\}\in E$. Finally, we verify the condition for $G$ (with $u=\{a\}$ and $v=\{a,b\}$, of course) and see that $x\in G$.
Therefore $G$ is precisely the set of all Kuratoski pairs of elements of $A$ and elements of $B$, in short $G=A\times B$.
While the above shows that all works out nicely, there is some way in which your doubt is justified: Suppose we have a set $X$ and a magical oracle that gives us what might be called a sub-collection $Y$ of $X$. Does that make $Y$ an element of $\mathcal P(X)$? Well, it does as long $Y$ is a set, but this may not be the case. In principle, it might happen that $Y$ is "undescribable" and the powerset only contains all "describable" subsets. But then again, $Y$ is not the subject of set theory because it fails to be set. The subset relation then exists only in a meta theory ... and fortunately there is no such thing as a magical oracle.