There are better bounds than the Azuma-Hoeffding bound for the tail probability of a Martingale . A good starting point is the classical inequality of Freedman (1975) [1]. But in the union bound for your question, only a constant factor is lost.
Let's see this in a more general context of estimating probability of a union of overlapping events in a probability space $(\Omega, {\cal F}, P)$. Let $A=\cup_{k=n}^M A_k$ where we allow $M$ to be infinity.
Define $\tau(\omega):=\infty$ for $\omega \in A^c$, and $\tau(\omega):=\min\{k: \omega \in A_k\}$ for $\omega \in A$.

[In the question, $A_k=\{X_k\le -k\}$.]

Write $S:=\sum_{k=n}^M {\bf 1}_{A_k}$, so $E(S)$ is exactly the union bound for $P(A)$.
We have
$$E(S)= P(A)E(S|A)=P(A)E[S|\tau<\infty]\,.$$
If the events $A_k$ arise from a Markov chain or a Martingale, one can often estimate the conditional expectation $E[S|\tau<\infty]$ quite well, by averaging over the value of $\tau$. For instance, in the question proposed by the OP,
we have $$\{\tau=k\} \Rightarrow \{ 1-k-c<X_k<-k\}$$, so for $ \ell >0$ we obtain
$$ P(A_{k+\ell} | \tau=k) \le \exp\Bigl(\frac{-(\ell-c)^2}{2\ell}\Bigr)<e^{c}e^{-\ell/2}\,,$$
whence
$$E[S| \tau=k] <B:=\frac{e^{c}}{1-e^{-1/2}}\,.$$
Since the RHS does not depend on $k$, we conclude that
$$E[S| \tau<\infty] <B \,.$$
and
$$P(A) >E[S]/B\,.$$

[1] Freedman, David A. "On tail probabilities for martingales." the Annals of Probability (1975): 100-118. [Cited 686 times according to Google scholar.]