R-LWE key exchange why using FFT instead of Karatsuba
First, as "Hope that's a start" mentioned, your citation is about the algorithms for multiplying integers, not polynomials. For polynomials, the FFT starts to be more efficient than Karatsuba and Toom-Cook methods much earlier, for polynomials of degree between (very roughly) a few hundreds and a few thousands.

However, for polynomials with integer coefficients, it is usually better to take the NTT (number theoretic transform) rather than the FFT, especially if those coefficients are considered modulo a certain $q$. First, you get no precision issues. Second, it is much faster. I have no idea why in the article you mentioned, the authors use FFT and not NTT, so it might be a good idea to ask them.

Now, to answer your question, the efficiency of NTT and Toom-Cook/Karatsuba methods are comparable for parameters equal to those you mentioned. Most lattice-based crypto implementation papers I have seen use the NTT (eg. New Hope), since the underlying rings are usually of the NTT-friendly form $\mathbb Z_q[x]/(x^{2^k}+1)$, and applications such as homomorphic encryption require bigger $n$'s, in which case NTT is clearly faster. That being said, I have seen efficients combinations of Karatsuba, Toom-Cook and schoolbook multiplication (eg. NTRU Prime) in lattice-based crypto.