Let me begin with an observation:

$2 \!\uparrow\uparrow\! n$ is equal to the number of sets of rank at most $n$.

[If you followed the combinatorics tag here and have forgotten what the rank of a set is, see this article for a refresher. Roughly, the rank of a set is the "depth" of the nesting of braces when it's written out in long form. For example, we have one set of rank $0$ (namely $\emptyset = \{\}$). There are two sets of rank $0$ or $1$ (namely $\{\}$ and $\{\{\}\}$), there are $4$ sets of rank at most $2$ (namely $\{\}$, $\{\{\}\}$, $\{\{\{\}\}\}$, and $\{\{\},\{\{\}\}\}$), there are $16$ of rank at most $3$, $65536$ of rank $\leq 4$, etc.]

This observation is easily proved by induction, and it gives us a natural answer to your Question 3 when we restrict ourselves to tetration with base 2.

What about the unrestricted version of Question 3?

For this, we want to stop viewing set membership as a binary relation (membership value of $0$ or $1$). Instead, let's allow $k$ possible membership values: a set can be a member of another with value $0$ (not a member), $k-1$ (fully a member), or anything in between.

For example, this view still gives us one set of rank $0$, namely the empty set $\{\}$, but now we have $k$ sets of rank $0$ or $1$, namely the sets containing only $\{\}$, with value between $0$ and $k-1$ (of course, the set containing $\{\}$ with value $0$ is identified with $\{\}$, so that we only get $k-1$ new sets of rank $1$, for a total of $k$ with rank $0$ or $1$). It is easy to check that we get $k^k$ "sets" of rank at most $2$, $k^{k^k}$ of rank at most $3$, and $k \!\uparrow\uparrow\! n$ sets of rank at most $n$.

So a plausible answer to your Question 3 is:

$k \!\uparrow\uparrow\! n$ is equal to the number of sets of rank at most $n$ when we adopt a $k$-valued notion of set membership.

One of the nice things about this answer is that it generalizes easily to higher cardinals.

As you know, the notion of $B$-valued set membership, where $B$ is some set (usually a Boolean algebra or a partial order) is a common one in set theory. Sets with a $B$-valued notion of membership are often called $B$-names, and they are naturally equipped with a notion of rank. In light of the foregoing discussion on finite tetration, I propose the following as a fairly natural definition for transfinite tetration:

$\kappa \!\uparrow\uparrow\! \nu$ is equal to the number of $B$-names of rank at most $\nu$, where $B$ is a set of size $\kappa$.

Notice that this definition coincides with the inductive definition in Noah's answer. One drawback to this definition (noticed already by Noah) is that the value of $\kappa \!\uparrow\uparrow\!\nu$ is determined by treating $\kappa$ as a cardinal while treating $\nu$ as an ordinal.

Right now, I can see two approaches to "fixing" this drawback: either live with it (it's not a bug, it's a feature!), or modify the definition to (something like)

$\kappa \!\uparrow\uparrow\! \nu$ is the number of $B$-names hereditarily smaller than $\nu$, where $B$ is a set of size $\kappa$.