There is the obvious combinatorial interpretation that follows from the definition of Stirling numbers: $a_{n,k}$ counts the number of ways you can take $n$ elements and partition them into some identical boxes, take those boxes and partition them into some identical boxes and so on $k$ times, in the end you use only one box. I'm not sure if this can help prove anything about the sequence combinatorially, though.
Edit: Actually there is a neat way to think about this interpretation in terms of trees. Let's call a rooted tree monotone if there are more vertices at depth $h+1$ than at $h$, for all $h$. h$, and for which all leaves are at the same distance from the root. Then by the previous paragraph, $a_{n,k}$ counts the number of monotone rooted trees of depth $k$ with $n$ leaves.
On What follows below can also be phrased in terms of the other handcorresponding combinatorial species, perhaps so if you think in terms of such trees you can prove these statements purely combinatorially.
Perhaps this can clarify the computational part of the question. Let
$$F=\text{diag}(0!,1!,2!,\dots)$$
and let
$$D(x)=(1,x,x^2,\dots)$$
also denote the Stirling matrix by $S=(p_{ij})_{i,j\geq 0}$, where $p_{ij}=S(i,j)$ if $i\geq j$ and $p_{ij}=0$ otherwise.
I might have my indexing off here but by looking at the (exponential) generating function of Stirling numbers the following is easy to check $$D(x)F^{-1}SF=D(e^x-1)$$ So that $$D(x)F^{-1}S^kF=D((e^x-1)^{(k)}),$$ where $f^{(k)}$ is $f$ composed $n$ times with itself. And the entries of the first column of $S^k$ are precisely the $a_{n,k}$ from which your statement that these are coefficients of the functional iterates of $e^x-1$, follows.
