1) Post the script/code/etc. you used, there is an error in it that perhaps readers can help you with: I whipped up the example in my CAS and it gets proper answer within the precision set.
2) The examples in that paper use multiples for each Pn, i.e., in its first example with comparisons in table 2, we have Pn of [.02,.04,.06,.08,.10], but there are 5 each accounted for, so you need to apply the calculation to the list of probabilities consisting of five repetitions of each value. Same with later examples. The result tables then show the true value and the various approximations that S(actual expected successes)<= s for some number of s successes, so you need to sum from 0 to s in your calculations to compare your results.
As previous posters stated, the Wikipedia DFT form is not an approximation, it is exact (modulo the capability of your computing system). It will take some serious cycles with large arguments - the form lends itself to using DFT tricks to speed calculations, but if you just implement it "as is" in say a CAS, you're not gaining much efficiency if any over the recursive form sans call stack space.
No, that isn't the way you correct for small sample normal approximation of the binomial. The correction is applied with respect to the fact that a sum of discrete probability masses doesn't behave the same as an integral of a continuous probability density.
For a simple example, suppose $X$ is discrete and $Y$ is a continuous approximation of $X$. The statement $\Pr[X = 2]$, assuming that $X$ can actually take on the value $2$ with some nonzero probability, is meaningful, but $\Pr[Y = 2] = 0$ because $Y$ is continuous. So, a naive approximation would be to say something like $$\Pr[X = 2] \approx \Pr[1.5 < Y \le 2.5].$$ We don't have to use $\pm 0.5$, of course, but it is one way to do such a continuity correction. It is worthwhile to note that such correction is completely independent of any parameters of the distributions themselves.
So, for the normal approximation to the binomial, let's try an example. Suppose $X \sim \operatorname{Binomial}(n = 53, p = 0.61)$. We wish to approximate this using a suitable normal distribution so that we may calculate $$\Pr[11 \le X < 35].$$ To this end, let $$Y \sim \operatorname{Normal}(\mu = np = 32.33, \sigma^2 = np(1-p) = 12.6087).$$ Then we have $$\begin{align*} \Pr[11 \le X < 35] &\approx \Pr[10.5 \le Y \le 34.5] \\ &= \Pr\left[\frac{10.5-32.33}{\sqrt{12.6087}} \le \frac{Y - \mu}{\sigma} \le \frac{34.5-32.33}{\sqrt{12.6087}} \right] \\ &= [-6.14778 \le Z \le 0.611117] \\ &= 0.729439 - 3.92865 \times 10^{-10} = 0.729439. \end{align*}$$ Take note of the direction of the correction: if $X$ includes the probability mass at one endpoint (here, $X = 11$ is included), the correction is adjusted to include the half-integer interval beyond it; if $X$ does not include the endpoint ($X = 35$ is not included), then the correction is adjusted to exclude the half-integer interval up to that value.
Without correction, the probability we would have obtained is $0.773953$. The exact probability, computed by summing $$\Pr[11 \le X < 35] = \sum_{x=11}^{34} \binom{53}{x} (0.61)^x (0.39)^{53-x} = 0.727048.$$ So as you can see, the continuity correction that was applied gives a far superior result.
Could you conceivably derive an adjustment to the normal mean and variance that performs as well as this method of correction? I strongly doubt it, for it would need to take into account whether you mean $$\Pr[\ell < X < u], \quad \Pr[\ell \le X < u], \quad \Pr[\ell < X \le u], \quad \Pr[\ell \le X \le u],$$ not to mention the values of $\ell$ and $u$ themselves in relation to the parameters $n$ and $p$. And even if it could be done, it is likely to be a more complicated algorithm to apply than what we have shown here.
Best Answer
The thing with approximations is that there is no hard and fast answer. There's no fixed rule as to what constitutes a large sample size or a small probability. For this course, I'd advise following your lecturer's guidance, but be aware of the fact that the notions of large and small are entirely arbitrary and subjective.
As for what to do in the situation where both poisson and normal approximations are valid, I'd advise asking your lecturer about that. Personally, I'd use both, since if the hypothesis is valid for one it should be valid for the other.