EDIT: We may assume that the Picard number is at least two, as otherwise the cone is simply a ray generated by any effective curve. In particular, every effective curve is extremal.
I will also assume that "curve" means "effective curve".
(This edit was prompted by Damiano's comment that is now (sadly) deleted. It was a useful contribution.)
A curve on a surface is simultaneously a curve and a divisor and assuming the surface is smooth or at least $\mathbb Q$-factorial, then the curve, as a divisor, induces a linear functional on $1$-cycles. This works better if the surface is proper, so let's assume that.
So, if $C$ is such a curve, then the corresponding linear function on the space where $NE(S)$ lives is best represented by the hyperplane on which it vanishes and remembering which side is positive and which one is negative.
If $C$ is reducible, then it may have negative self-intersection, but it is not extremal. For an example, blow up two separate points on a smooth surface and take the sum of the exceptional divisors. My guess is that you meant irreducible, so let's assume that.
Now we have $3$ cases:
$C^2>0$. In this case $C$ is in the interior of the cone and it cannot be extremal, can't even be on the boundary (Use Riemann-Roch to prove this).
$C^2=0$. Since $C$ is irreducible, it follows that it is nef and hence a limit of ample classes, so it is effective, but as Damiano pointed out I have already assumed that. (It is left to the reader to rephrase this if $C$ is assumed to be nef instead of effective). In this case the hyperplane corresponding to $C$ as a linear functional is a supporting hyperplane of the cone, intersecting it at least in the ray generated by $C$. So $C$ is definitely on the boundary, but it may or may not be extremal depending on the surface. For example any curve of self-intersection $0$ on an abelian surface is extremal, but for instance a member of a fibration that also has reducible fibers is not extremal despite being irreducible. For the latter think of a K3 surface with an elliptic fibration that has some $(-2)$-curves contained in some fibers.
$C^2<0$. If $C$ is effective, then $C\cdot D>0$ for any irreducible curve $D\neq C$. This means that $C$ and all other irreducible curves lie on different sides of the hyperplane corresponding to $C$ as a linear functional, so the convex cone they generate must have $C$ generating an extremal ray.
Observe that we did not use the Cone Theorem. In fact one gets a different "cone theorem" this way:
Theorem
Let $S$ be a smooth projective surface $H$ an arbitrary ample divisor on $S$ and let
$$
Q^+=\{\sigma\in N_1(S) \vert \sigma^2 >0, H\cdot\sigma \geq 0 \}
$$
be the "positive component" of the interior of the quadric cone defined by the intersection pairing. Then
$$
\overline{NE}(S) = \overline{Q^+} + \sum_{C^2<0} \mathbb R_+[C]
$$
There is also one for $K3$'S, using the above notation:
Theorem
Let $S$ be a smooth algebraic K3 surface and assume that its Picard number is at least $3$. (If the Picard number is at most $2$, then there are not too many choices for a cone).
Then one of the following holds:
(i)
$$
\overline{NE}(S) = \overline{Q^+}, or
$$
(ii) $$
\overline{NE}(S) = \overline{\sum_{C\simeq \mathbb P^1, C^2<0} \mathbb R_+[C]}.
$$
The two cases are distinguished by the fact whether there exists a curve in $S$ with negative self-intersection. If the Picard number is at least $12$, then only (ii) is possible.
For proofs and more details, see The cone of curves of a K3 surface.
(There is also a newer version which is less detailed, but works in arbitrary characteristic. See here or here.)
Answer: no. Example: take a simple abelian surface X with real multiplication by Q($\sqrt{d}$) (where d is a square-free positive number). X has Picard number 2, and the intersection form on N^1(X) diagonalises over Q to diag(a,-b) where b/a=d. The nef cone is just the cone of classes x in N^1(X) with x^2 >= 0 (more precisely, the part of this cone which also satisfies x.h >=0 for a chosen ample class h), and a simple computation shows that the boundary rays of this cone are irrational (by square-freeness of d). Now for any abelian variety the effective cone is equal to the nef effective cone, which equals the union of the ample cone with the rational boundary faces of the nef cone. In our example the nef cone has no rational boundary faces, so the ample cone and the effective cone (minus zero) coincide.
Best Answer
As J.C. indicates in the comments, an example for Q1 can be gotten from the variety considered in this paper. This isn't spelled out in the paper, so let me explain it here.
First let's change the question into its dual form. The cone of curves is dual to the nef cone, and Boucksom--Demailly--Peternell--Paun showed that the cone of moving curves is dual to the cone of pseudoeffective divisors. So we want to find an example of $X$ such that $Nef(X)$ is rational polyhedral but the cone of pseudoeffective divisors $PsEff(X)$ isn't.
I claim the variety $X$ in the linked paper is such an example. Here, $X$ is constructed by blowing up $\mathbf{P}^3$ at the base locus of a general net of quadrics.
The variety $X$ is then elliptically fibred over $\mathbf{P^2}$, with the generic fibre having an infinite abelian group (more precisely, rank 8) of sections. Call this group $MW(X)$. Translating by differences of sections gives an action of $MW(X)$ on $X$ by so-called pseudo-automorphisms (meaning birational automorphisms that are isomorphisms in codimension 1). This group action preserves effective divisors, and hence the cone $PsEff(X)$. One can calculate the action fairly explicitly, and in particular one sees the orbit of a divisor $E_i$ (the exceptional divisor of one of the blowups) in N^1(X) is infinite. Now it is easy to see that each $E_i$ spans an extremal ray of $PsEff(X)$, and hence so does any $MW$-translate of $E_i$; since there are infinitely many of these, $PsEff(X)$ has infinitely many extremal rays.
On the other hand, it's not hard to show that $Nef(X)$ is rational polyhedral. This is done more or less by brute force: enumerate some curve classes, find the dual cone to the convex hull of those classes (which is then an upper bound for $Nef(X)$), and check that it's spanned by nef classes. Details are in the paper.