I am trying to find the stability of $h(n) = 4^nu[-n-1]$ using Z-transform.
First I looked at Z=transform pairs but it resembles none of the Z-transform pairs.
$$a^nu[n]\Longleftrightarrow \frac{1}{1-a \cdot z^{-1}}, \lvert z\rvert>\lvert a\rvert$$
$$-a^nu[-n-1]\Longleftrightarrow \frac{1}{1-a\cdot z^{-1}}, \lvert z\rvert<\lvert a\rvert$$
Therefore, I will calculate Z-transform from the beginning:
$$\sum_{n= -\infty}^\infty 4^n\cdot u[-n-1] \cdot z^{-n}$$ $$\sum_{n=-\infty}^{-1} 4^n \cdot z^{-n} $$ $$\sum_{n=1}^{\infty} 4^{-n}\cdot z^{n} $$
As far as I know: $$\frac{a_1}{1-r}=\frac {\frac{z}{4}}{1-\frac{z}{4}}=\frac{-1}{1-4 \cdot z^{-1}}$$
When it is in the $\frac{1}{1-a \cdot z^{-1}}$ form, I know how to check stability.
However, I am not sure how to find stability if there is a minus sign before the result.
Ok, let us first stablish somethings just by looking at the signal:
1) The $u[-n-1]$ step function indicates that the system has values $\neq 0$ only for negative values of $n$, what means it is anticausal.
2) If it is anticausal, then its $ROC$ looks like this: $|z|\lt r$
Having this in mind, we can follow up your steps to find the Z-tansform of the system:
$$ \begin{align} \mathcal{Z}\{h(n)\}=H(z)&= \sum_{k= -\infty}^\infty 4^k\cdot u[-k-1] \cdot z^{-k}\\ &=\sum_{k=-\infty}^{-1} 4^k \cdot z^{-k}\\ &=\sum_{k=1}^{\infty} 4^{-k}\cdot z^{k}\\ &=\sum_{k=1}^{\infty} \left(\frac{z}{4}\right)^k \end{align} $$
Here we can confirm that the series converges for: $$|z|\lt 4$$
As you stated, this converges to the infite geometric progression sum:
$$\frac{a_{1}}{1-q}$$
Where, in our case we have: $a_{1}=q=\frac{z}{4}$, so:
$$ \begin{align} H(z)&=\frac{\frac{z}{4}}{1-\frac{z}{4}}\\ &=\frac{z}{4-z}\\ &=\frac{1}{4z^{-1}-1}\\ &=-\frac{1}{1-4z^{-1}} \end{align} $$
This way, for this system we have: Zeros:$\{0\}$ and Poles:$\{4\}$
The unit circle $|z|=1$ is in the $ROC$ of this system, which is a fundamental requirement for stability, and, once $|z|\lt 4$ does not contain $4$, the poles are outside the $ROC$.
Therefore, this system is stable.
Regarding your doubt on how to treat the minus sign, it does not change the result about the poles, look:
$$ \begin{align} 1-4z^{-1}&=0 & 4z^{-1}-1&=0\\ 4z^{-1}&=1 & 4z^{-1}&=1\\ z=&4 & z&=4 \end{align} $$