Apply the product-to-sum identity to turn each term into a difference of two sine terms

The sum telescopes to $\sin(n(n+1)a),$ which is an integer exactly when $n(n+1)$ is a multiple of $1004$

By the product-to-sum identity, $$\begin{aligned} &2\cos(k^2 a)\sin(ka) \\ &= \sin(k^2 a + ka) \\ &\quad {}- \sin(k^2 a - ka) \\ &= \sin(k(k+1)a) \\ &\quad {}- \sin((k-1)k a). \end{aligned}$$ Summing over $k = 1$ to $n,$ the terms telescope, leaving $$\sin(n(n+1)a) = \sin\frac{n(n+1)\pi}{2008}.$$

A sine is an integer only when it is $-1,$ $0,$ or $1,$ that is, when its argument is a multiple of $\frac{\pi}{2}.$ So we need $\frac{n(n+1)}{2008}$ to be a multiple of $\frac{1}{2},$ i.e. $n(n+1)$ is divisible by $1004,$ where $1004 = 4 \cdot 251$ and $251$ is prime.

Since $n$ and $n + 1$ are coprime, $251$ must divide one of them, so $n \ge 250.$ For $n = 250$ the product $250 \cdot 251$ is not divisible by $4.$ For $n = 251$ the product $251 \cdot 252$ is divisible by $4 \cdot 251 = 1004.$ The smallest such $n$ is $251.$