Here is a crude upper bound. It might not be good enough for what you are after, but without further constraints on your matrices, it is hard to see how one can do substantially better.
Throughout, I am using the operator norm. $\newcommand{\norm}[1]{\Vert#1\Vert} \newcommand{\Cplx}{{\bf C}}\newcommand{\lm}{\lambda}$
Fix $k$. Let $A$ be a $k\times k$ matrix with complex entries. Schur's theorem from linear algebra tells us that there is an upper triangular matrix $B$ and a unitary matrix $U$ such that $A=U^*BU$.
Let $d_1,\dots, d_n$ be the diagonal entries of $B$ (these form the spectrum of $B$, and hence of $A$, as we will shortly see). For $\lm\in\Cplx\setminus\{d_1,\dots,d_n\}$, let $D_\lambda$ be the diagonal matrix whose entries are $(\lm_1-d_1)^{-1}, \dots, (\lm_k-d_k)^{-1}$, and put $ C_\lm = D_\lm^{-1} (\lm I - B) $ Then $C_\lambda$ is an upper triangular matrix with each diagonal entry equal to $1$. Since $(C_\lm - I)^k=0$, $C_\lm$ is $I$ + a nilpotent matrix, and so is invertible. In fact, just by the usual formula for $(1+x)^{-1}$, we have $ C_\lm^{-1} = \sum_{j=0}^{k-1} (-1)^j(C_\lm-I)^j $ and thus $ (\lm I- B)^{-1} =(D_\lm C_\lm)^{-1} = \sum_{j=0}^{k-1} (-1)^j(C_\lm-I)^j D_\lm^{-1} $
Now we just use the triangle identity and submultiplicativity of the norm. Let $d(\lm) = {\rm dist}(\lm, \sigma(B)) = \min_j \vert d_j-\lm\vert$. Then $\norm{D_\lm^{-1}} = d(\lm)^{-1}$, and $ \norm{ (\lm I- B)^{-1} } \leq \sum_{j=0}^{k-1} d(\lm)^{-j-1} \norm{\lm I - B}^j = d(\lm)^{-1} \frac{d(\lm)^{-k}\norm{\lm I - B}^k - 1}{d(\lm)^{-1}\norm{\lm I-B} -1 } . $ Since $B$ is unitarily equivalent to $A$, the same inequality holds with $B$ replaced by $A$.