When does f-nef imply nef (after twisting?)

Let $f=\alpha\circ g$ the Stein factorization of $f$ with $g:X\to W$ having connected fibers and $\alpha:W\to Z$ finite.

Let $x\in {\rm supp}\, D\subset X$ and $w=f(x)$ and let $C\subseteq X_w=g^{-1}(w)$ such that $x\in C$. Since $-D\cdot C\geq 0$ this means that $C\subseteq {\rm supp}\, D$. Therefore, ${\rm supp}\, D$ is a union of $g$-fibers. In particular $g({\rm supp}\, D)$ is not dense in $W$ and hence $f({\rm supp}\, D)$ is not dense in $Z$. Now let $B$ be an effective reduced Weil divisor on $Z$ containing $f({\rm supp}\, D)$. Further let $A$ be a sufficiently very ample divisor on $Z$ such that $A-B$ is effective.

Now $f^*(mA)-D$ for $m\gg 0$ can be written as the pull-back of a very ample divisor from $Z$ plus an effective divisor supported entirely on fibers of $f$. This implies that it will have non-negative intersection with any curve that is not contained in a fiber. On the other hand $f^*({\rm anything})$ is trivial on fibers, so the intersection of $f^*(mA)-D$ with any curve that is contained in a fiber is the same as the intersection of $-D$ with that curve and hence non-negative. This shows that $f^*(mA)-D$ is indeed nef.

EDIT: 1) added applying Stein factorization first to account for the possibility that the fibers of $f$ are not necessarily connected. 2) Corrected the statement that $f({\rm supp}\, D)$ is a divisor to that it is contained in a divisor. 3) Thanks for the constructive comments, especially Artie!

I do not know the answer in general.

However, when $X$ is a surface and $Z$ is a curve, it is not difficult to see that the only possibility, in the case you are interested in, is

$D=\mathcal{q}F$,

where $F$ is the class of a fiber of $f \colon X \to Z$ and $q \in \mathbb{Q}$.

In fact, since we are assuming that $-D$ is $f$-nef, we must have $-DF \geq 0$. Writing $D=D_1+D_2$, where $D_1$ is the maximal subdivisor contained in fibres of $f$, we obtain $D_1F=0$, $D_2F > 0$, hence

$D=D_1$ and $D_2= \emptyset$,

in particular $DF=0$ and $D^2 \leq 0$ by Zariski lemma.

Now assume that $-D+nF$ is nef for some $n \geq 1$; then

$0 \leq (-D+nF)^2=D^2$,

thus $D^2=0$. Again by Zariski lemma, $D$ must be a rational multiple of $F$.

The following is maybe obvious, and isn't exactly what you asked, but perhaps is still worth spelling out.

As Sándor's answer shows, if $L=O_X(-D)$ is $f$-nef (where $D$ is effective) then in fact $D$ must be pulled back from $Z$, so $L$ belongs to the subspace $f^\ast(N^1(Z))$ of $N^1(X)$. In general, for any class $f^\ast L$ in $f^\ast(N^1(Z))$ we can twist with a line bundle $f^\ast(A)$ (where $A$ is a sufficiently ample bundle on $Z$) to get something nef, because $A+L$ is ample on $Z$ for sufficiently ample, and then $f^\ast(A+L)$ is nef --- indeed, it's even semi-ample.

So we only have a problem when there are f-nef classes which are not pulled back from $Z$. In particular, we can have a problem when the subspace $K$ of f-numerically trivial classes is strictly bigger than $f^\ast(N^1(Z))$.

This is what happens in the example you cite from Lazarsfeld: there $K$ has dimension 2, whereas $f^\ast(N^1(Z))$ has dimension 1 (since $Z$ is a curve). Drawing a picture of what happens there is instructive, and explains why the f-ample and f-nef cases behave differently. The nef cone of $X$ is a 3-dimensional round cone, and $K$ is a 2-dimensional subspace of $N^1(X)$ which lies tangent to the cone. They meet in a single ray, which is exactly $f^\ast(Nef(Z))$. It's geometrically clear that starting from a point on $K$ which is not on the line $f^\ast(N^1(Z))$ and adding elements of $f^\ast(Nef(Z))$, we can never get into the nef cone; on the other hand, starting with an f-ample class, which means exactly a point in the open half-space on the same side of $K$ as the nef cone, and moving in the direction of $f^\ast(Nef(Z))$, we eventually end up in the interior of $Nef(X)$, i.e. in the ample cone.

Here is my amateurish attempt to illustrate that:
Nef http://www.freeimagehosting.net/uploads/f7858c4e0d.jpg