You seem to be under some misconception here: no smooth curve of genus $2$ is planar, actually!
Indeed, a plane curve has a degree $d$ and if it is smooth its genus is then $g=\frac {(d-1)(d-2)}{2}$.
So actually most smooth curves are non-planar because most integers are not of the form $\frac {(d-1)(d-2)}{2}$.
The smallest example is, as I said, $g=2$ but also smooth curves of genus $4,5,7,8,9,\ldots $ are all non-planar (this answers your question about $g=4$).
Also: all smooth plane curves of degree $4$ have indeed genus $3$, but some curves of genus $3$ are not planar, namely the hyperelliptic ones.