Why is the following language not context-free?
Your first approach is not very clear. What are $n$ and $m$? You have to fix a word in order to use the Pumping lemma; please see our reference question for how it's done.

Your second approach is fundamentally flawed as CFL is not closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^*b^*$.

Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^* b^*)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be

$\qquad L' = \{a^n b^m \mid m = n^2\}$.

It is easy to show that $L'$ is not context-free by using the Pumping lemma.