I believe what you would like is true
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 $z=f(z)$ w=f(x)$ and let $C\subseteq X_z$ 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 fibers. $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 a an effective reduced Weil divisor on $Z$ containing $f({\rm supp}\, D)$. By the above, this is indeed possible. Further let $A$ be a sufficiently very ample divisor on $Z$ such that ${\rm supp}\, A\supseteq {\rm supp}\, D$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$ and 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!
