Well, you could define $(a,b,c)$ as $((a,b),(c,c))$, and then it is an element of $\mathscr{P}^4(X)$. More generally, if $n\leq 2^m$, you can represent $n$-tuples as a tree of $m$-tuply nested ordered pairs, and thus as elements of $\mathscr{P}^{2m}(X)$. This shows that $$k^n\leq f^{2\lceil \log_2 n\rceil}(k)$$ where $f(x)=2^x$. (Of course, this bound can also be obtained by just iterating $k^2\leq 2^{2^k}$ to get $k^4=(k^2)^2\leq (2^{2^k})^2\leq 2^{2^{2^{2^k}}}$ and so on.)
You can do better at least in some cases, though. For instance, you can represent triples in $\mathscr{P}^3(X)$ by defining $(a,b,c)$ as $\{(a,b),(a,c),(b,c)\}$. More generally, you can represent an $n$-tuple as the set of all the $(n-1)$-tuples obtained by deleting one entry in the $n$-tuple (for any $n>2$), so inductively this represents $n$-tuples as elements of $\mathscr{P}^n(X)$. This gives the bound $$k^n\leq f^n(k),$$ which is better than the previous bound for $n=3$ and $n=5$. Or, you can use the earlier representation of $2^m$-tuples as elements of $\mathscr{P}^{2m}(X)$ to represent $(2^m+1)$-tuples as elements of $\mathscr{P}^{2m+1}(X)$, which is slightly better than the $\mathscr{P}^{2m+2}(X)$ that would be given by the first method.
To prove that this works, let $s$ be an $n$-tuple and let $R$ be the set of $(n-1)$-tuples obtained by removing an entry from $s$; we will recover $s$ from $R$. If all elements of $R$ have the same first entry (say, $a$), then $a$ must be the first entry of $s$. Moreover, there is then a unique element of $R$ which starts with fewer $a$s than every other element of $R$ (namely the $(n-1)$-tuple obtained by removing the first entry of $s$), and that element is the remaining $n-1$ entries of $s$.
So, we may assume that not all elements of $R$ have the same first entry. If there is some $a$ such that two different elements of $R$ start with $a$, then $a$ must be the first entry of $s$ and the remaining entries are given by the unique element of $R$ that doesn't start with $a$. Thus, we may assume that $R$ has only two different elements, say one starting with $a$ and another starting with $b$. But this means the entries of $s$ can only be $a$ and $b$ (if $s$ had three distinct entries, they would give three distinct elements of $R$). Moreover, all the $a$s must be consecutive, since removing $a$s in different consecutive blocks would give different elements of $R$, and similarly the $b$s must be consecutive. We can count how many $a$s there are in $s$ (the maximum that there are in any element of $R$) and similarly for the $b$s, and we can tell whether the $a$s come first or the $b$s come first since $n>2$. Thus, we can recover $s$ from the set $R$.
For $n=3$, at least, this is optimal in the following sense: it is impossible to represent ordered triples as elements of $\mathscr{P}(\mathscr{P}(X))$ (by a formula that sends a triple $(a,b,c)$ to some doubly nested set expression in $a,b,$ and $c$). Clearly such a representation of a triple $(a,b,c)$ would have to involve all three of $a,b,$ and $c$. But now consider the 6 triples $(a,a,b),(b,b,a),(a,b,a),(b,a,b),(b,a,a),(a,b,b)$. Each of these must be represented by a distinct element of $\mathscr{P}(\mathscr{P}(\{a,b\}))$ which is not fixed if you swap $a$ and $b$. Thus, each one must contain exactly one of $\{a\}$ and $\{b\}$. This means that each one also must contain $\{a,b\}$, since the formula for $(a,b,c)$ must involve all three of $a,b,$ and $c$. But now we have a problem: there are only 4 different subsets of $\mathscr{P}(\{a,b\})$ satisfying this constraint, so our 6 triples cannot all be distinct.
In each case one can uniquely recover the components and their order from the $n$-tuple. Suppose, for example, that $t\in A\times B\times C$ is a Kuratowski ordered triple. Then there are a unique $p\in A\times B$ and $c\in C$ such that $t=\langle p,c\rangle$, and there are unique $a\in A$ and $b\in B$ such that $p=\langle a,b\rangle$. Thus, we can read off the first, second, and third components of $t$ as $a,b$, and $c$, respectively: $t=\langle a,b,c\rangle$.
Mind you, actually describing how to recover $a$ and $b$ from $p$, for instance, is a bit of a pain, but it can be done. First, $a$ is the unique $x\in\bigcup p$ such that $\forall y\in p\,(x\in y)$. If $a$ is the only element of $\bigcup p$, then $b=a$; otherwise, $b$ is the unique element of $\left(\bigcup p\right)\setminus\{a\}$.
From the other definition, of course, we recover $a,b$, and $c$ as $t(0),t(1)$, and $t(2)$, respectively. The bijection between the two versions of $A\times B\times C$ is then defined in terms of the components: if $\langle a,b,c\rangle$ is a Kuratowski triple, the indexed set triple corresponding to it under the bijection is the unique $t$ in the indexed set product such that $t(0)=a$, $t(1)=b$, and $t(2)=c$.
All of this generalizes readily to $n$-fold products for arbitrary $n\in\Bbb Z^+$.
Best Answer
So, to first answer your main question:
And the answer is, yes, absolutely. If someone put forth some notion of ordered pairs, and there was not some way of extracting the $x$ from $(x, y)$, we would tell them to go away and come back when they had something useful. So yes, we can do this with Kuratowski pairs. You can find the formulas in the Wikipedia article on “ordered pair”. As you surmised, $\Fst(p)$ is just $\bigcup\bigcap p$. The corresponding ${\rm Second}(p)$ is unfortunately rather more complicated.
But you should know there is nothing really special about the Kuratowski formula $$(x, y) = \{\{x\}, \{x, y\}\}.$$ It was not the first or only set-theoretic model of ordered pairs. It was preceded historically by Norbert Wiener's definition:
$$(x, y) = \{\{\{x\},\emptyset\}, \{\{y\}\}\}$$
and by Felix Hausdorff's:
$$(x, y) = \{\{1, x\}, \{2, y\}\}$$
which incidentally looks rather a lot like what you wanted to do:
Hausdorff's pair isn't a function with domain $\{1, 2\}$, but it almost looks like one, and Hausdorff's motivation was probably similar to yours. It's a very natural idea!
But there's an important technical problem with your suggestion to represent an $n$-tuple as a function. The problem is that in set theory, functions are usually modeled as sets of pairs. The function $$\begin{array}{rl} 1\to&\text{Fish} \\ 2\to&\text{Carrot} \\ \end{array}$$
is usually understood as being equal to the set
$$\{(1, \text{Fish}), (2, \text{Carrot})\}$$
Where the $(x, y)$ expressions are ordered pairs. So you have to have pairs before you have functions. If you want the ordered pairs to also be functions, you are stuck in a loop: you have defined ordered pairs as functions, but defined functions as sets of ordered pairs.
To make your idea work you would need to to find some way of defining what a function is without using ordered pairs, or you would need to make an exception for pairs, and posit that $n$-tuples should be functions when $n>2$, but are Kuratowski sets (or whatever) when $n=2$.
But now I come to the real point:
Kuratowski's definition is most often used because in some ways it is simplest; certainly it is easy to write down. But there is nothing special about it. Notice that $(x, y) = \{\{y\}, \{x, y\}\}$ would clearly work just as well as the usual $(x,y) = \{\{x\}, \{x, y\}\}$.
What is important in set theory is only that there be some method for representing the pair $(x, y)$ as a set so that these three properties hold:
Kuratowski's definition satisfies these requirements, and so do Wiener's and Hausdorff's and many others. Once we've proved that the three properties hold, we usually forget about the internal details of exactly what set is meant by $(x, y)$. Wiener's original paper says “the particular method selected of doing this is largely a matter of choice”. As long as there is some set that behaves the way we want the pair $(x, y)$ to behave, we don't actually care very much what that set is.
Here's how it was put by J.H. Conway, a famous mathematician, who seemed rather frustrated by the insistence that every entity in his theory be representable as some specific set in ZF:
(J.H. Conway, On Numbers and Games, 2 ed. (2001) p.66)
Finally, I would like to note that the basic philosophy of the extremely successful branch of mathematics called category theory is that these internal details matter so little that one can—and should—forget about them entirely!
In category theory, one says that a set (or other object) $C$ “is a product of $A$ and $B$”, meaning that it is something like the set of pairs of elements of $A$ and $B$. This object $C$ is considered to be such a product if two required functions $$\text{First} : C\to A\\\text{Second} : C\to B$$ exist and have certain properties that I won't go into. Whether $C$ is a set of Kuratowski pairs or Wiener pairs or something else is of absolutely no interest in category theory, so long as we can identify satisfactory $\text{First}$ and $\text{Second}$. The phrasing “$C$ is a product of $A$ and $B$” rather than “$C$ is the product of $A$ and $B$” is intended to emphasize this.
Category theory is successful precisely because it ignores the unimportant details of what is going on inside the particular project object. If it has a suitable $\text{First}$ and $\text{Second}$, that is good enough. (Category theorists usually call these $\pi_1$ and $\pi_2$, but the idea is exactly the same.)
Well, that is probably far more than you wanted to know.
(By the way, you are using the term “predicate” incorrectly. A predicate function is one that yields true or false. For example, “$x$ is an even number” is an example of a predicate, and so is “The first component of the pair $p$ is equal to $7$”. But “The first component of the pair $p$” is not a predicate.)