Same z transformed function, but different answers of inverse z transform?
Here's a much simpler method. We have

$$E (z) := \frac{1}{z+4} = z^{-1} \left(\frac{1}{1 - (-4) \, z^{-1}}\right)$$

which we assume to be the $\mathcal Z$ transform of a causal discrete-time signal. Consulting a table of $\mathcal Z$ transforms, we conclude that

$$\mathcal Z^{-1} \left\{ \frac{1}{1 - (-4) \, z^{-1}} \right\} = (-4)^n \, u (n)$$

where $u$ is the discrete-time step function. Hence, the inverse $\mathcal Z$ transform of $E$ is simply the discrete-time signal above after a unit delay, i.e.,

$$e (n) = (-4)^{n-1} \, u (n-1)$$

which is zero at $n=0$. Hence, your 1st candidate answer is (almost) correct. Your 2nd candidate answer is only correct if $n \geq 1$. When working with functions, do not forget what their domains are.