Estimate for tail of power series of exponential function?

Let's instead consider the sum

$$ \sum_{k = A + C \sqrt{A}}^\infty {e^{-A} A^k \over k!} $$ which of course differs from yours just by a factor of $e^{-A}$.

Then this sum is the probability that a Poisson random variable of mean $A$ is at least $A + C\sqrt{A}$.

A Poisson with mean $A$ has standard deviation $\sqrt{A}$, and as $A \to \infty$ the Poissons become asymptotically normal. So we have

$$ \sum_{k = A + C \sqrt{A}}^\infty {e^{-A} A^k \over k!} \to \Phi(C) $$

as $A \to \infty$, where $\Phi$ is the CDF of the standard normal. So your sum is asymptotic to $e^A \Phi(C)$.

Alternatively, if you'd like an explicit inequality, your sum can be bounded above by the geometric series with first term $A^B/B!$ and common term ratio $A/B$. Therefore, your sum is less than $$ {A^B \over B!} {1 \over 1-A/B} $$ and this can be rewritten as $$ {A^B \over B!} \left( 1 + {\sqrt{A} \over C} \right) $$ The product $A^B/B!$ is, as $A \to \infty$ with $B = A + C \sqrt{A}$, $$ {1 \over \sqrt{2\pi}} e^{-C^2/2} A^{-1/2} e^A (1+o(1))$$ by Stirling's formula. In the factor $1 + \sqrt{A}/C$ we can neglect $1$ as $A \to \infty$, so we get that

$$ \sum_{k = A+C\sqrt{A}}^\infty {e^{-A} A^k \over k!} \le {1 \over \sqrt{2\pi}} C e^{-C^2/2} e^A (1 + o(1)) $$

By, say, the double inequality (26) here it should be possible to get explicit bounds.

The exponential inequality yields explicit bounds as follows. For every $B\ge A$, consider the series $$ S(A,B)=\sum_{k=B}^{+\infty}\frac{A^k}{k!}. $$ Then, as Michael Lugo noticed, $\mathrm{e}^{-A}S(A,B)=P(N_A\ge B)$, where $N_A$ is a Poisson random variable with parameter $A$.

For every positive $t$, $N_A\ge B$ if and only if $\mathrm{e}^{tN_A-tB}\ge1$, and for every nonnegative random variable $X$, $P(X\ge1)\le E(X)$. Using this for $X=\mathrm{e}^{tN_A-tB}$, one gets $$ \mathrm{e}^{-A}S(A,B)\le E(X)=E(\mathrm{e}^{tN_A})\ \mathrm{e}^{-tB}. $$ To go further, one uses the fact that the Laplace transform $E(\mathrm{e}^{tN_A})$ of a Poisson distribution is $\mathrm{e}^{A(\mathrm{e}^t-1)}$ and one optimizes the upper bound with respect to $t\ge0$. That is, one plugs in the inequality the value of $t$ such that $\mathrm{e}^t=B/A$, which yields $$ S(A,B)\le\mathrm{e}^{B-B\log(B/A)}. $$ Note that this upper bound is not asymptotic (which is nice) but that, in general, it is not optimal in the regime of the central limit theorem you are interested in (which is not so nice).

Turning to the case where $A\to\infty$ and $B=A+C\sqrt{A}$ with $C>0$ fixed, the expansion of $\log(B/A)$ up to the order $o(1/A)$ yields $$ S(A,A+C\sqrt{A})\le\mathrm{e}^{A-C^2/2+o(1)}=\mathrm{e}^{-C^2/2}\mathrm{e}^A(1+o(1)). $$ Which is a (very odd) way to check that $\Phi(C)\le\mathrm{e}^{-C^2/2}$...

Edit : Non asymptotic upper bound : $$ S(A,A+C\sqrt{A})\le\mathrm{e}^{-C^2/2}\mathrm{e}^{A}\exp(C^3/(2\sqrt{A})). $$