One option, in particularly if one knows (roughly) what to expect is to attack it from the other side. If we didn't already know what to expect, we could shape our expectation by considering the case where $k = -m$ is a negative integer. Then the plain semicircular contour works, and we obtain
$$\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} e^{st}s^{-m}\,ds = \operatorname{Res}\left(e^{zt}z^{-m};0\right) = \frac{t^{m-1}}{(m-1)!},$$
which suggests we look at $\frac{t^{m-1}}{\Gamma(m)}$ also for non-integer $m > 0$. Indeed, considering real $s > 0$ in the Laplace integral to have no problems with substitution, we find
$$\int_0^\infty t^{m-1}e^{-st}\,dt = \frac{1}{s^m}\int_0^\infty u^{m-1}e^{-u}\,du = \frac{\Gamma(m)}{s^m},$$
and by the identity theorem that holds for all $s$ with $\operatorname{Re} s > 0$, so indeed $\frac{t^{m-1}}{\Gamma(m)} = \frac{t^{-(k+1)}}{\Gamma(-k)}$ is the inverse Laplace transform of $s^k$ for any $k < 0$, integer or not.
When we use the contour wrapping the branch-cut, note that the integral over the part $C_4$ only tends to $0$ in the limit if $-1 < k < 0$.
For the integral over $C_3$, in the limit moving the path to the negative real axis, we get $\operatorname{Log} s = \log \lvert s\rvert + i\pi$, so
$$\begin{align}
\int_{C_3} e^{st}s^k\,ds &\to \int_{-R}^{-\varepsilon} e^{st} \exp\left(k(\log (-s)+i\pi)\right)\,ds\\
&= e^{ik\pi}\int_{-R}^{-\varepsilon} e^{st}\lvert s\rvert^k\,ds.
\end{align}$$
Similarly, on $C_5$ the logarithm becomes $\log \lvert s\rvert -i\pi$, and
$$\begin{align}
\int_{C_5}e^{st}s^k\,ds &\to -\int_{-R}^{-\varepsilon} e^{st}\exp\left(k(\log(-s)-i\pi)\right)\,ds\\
&= -e^{-ik\pi}\int_{-R}^{-\varepsilon} e^{st}\lvert s\rvert^k\,ds.
\end{align}$$
Together,
$$\int_{C_3+C_5} e^{st}s^k\,ds \to 2i\sin(k\pi)\int_{\varepsilon}^R e^{-xt}x^k\,dx.$$
For $-1 < k < 0$, we can take the limit as $\varepsilon\to 0$ and $R\to\infty$ and obtain
$$\frac{1}{2\pi i} \int_{C_3+C_5} e^{st}s^k\,ds \to \frac{\sin (k\pi)}{\pi}\frac{\Gamma(k+1)}{t^{k+1}}.$$
By Euler's reflection formula for the $\Gamma$-function and the functional equation $\Gamma(z+1) = z\Gamma(z)$,
$$\frac{\sin (k\pi)}{\pi} = \frac{1}{\Gamma(k)\Gamma(1-k)} = \frac{1}{\Gamma(k)(-k)\Gamma(-k)} = -\frac{1}{\Gamma(k+1)\Gamma(-k)},$$
so
$$\frac{1}{2\pi i} \int_{C_3+C_5} e^{st}s^k\,ds \to -\frac{t^{-(k+1)}}{\Gamma(-k)},$$
and since the integral over the entire contour vanishes by Cauchy's integral theorem,
$$\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} e^{st}s^k\,ds = \frac{t^{-(k+1)}}{\Gamma(-k)},$$
which we already saw above.
For $k$ a negative integer, the integrals over $C_3$ and $C_5$ cancel in the limit, and the integral over $C_4$ becomes the residue in $0$ (times $2\pi i$). For $k < -1$ not an integer, the limit as $\varepsilon\to 0$ of the integral over $C_4$ does not exist, nor does the limit of the integral over $C_3+C_5$. But for the integral over $C_3+C_4+C_5$, by $\lfloor -k\rfloor$ integrations by part, we obtain the result.
