Higher cohomology of sheaves on a projective space Let $S\subset\mathbb{P}^n$ be a finite set of $s$ reduced points. Let $\mathcal{I}$ be the ideal sheaf of $S$ in $\mathbb{P}^n$. We consider the sheaf 
$$\mathcal{F}_k:=\mathcal{O}_{\mathbb{P}^n}(kd)\otimes\mathcal{I}^{km}.$$
Therefore $H^{0}(\mathbb{P}^n,\mathcal{F}_k)$ is the space of hypersurfaces of degree $kd$ with points of multiplicity at least $km$ at any point of $S$. If $\pi:X\rightarrow\mathbb{P}^n$ is the blow-up of $S$ and $D = dH-mE_1-...-mE_s$ we have
$$\pi_*\mathcal{O}_X(kD) = \mathcal{F}_k.$$
Is it true that $H^{i}(X,\mathcal{O}_X(kD)) = 0$ for $i>0$ and $k\gg 0$ ?
 A: No.  Take $n=2$, $s=2$, $D = H - E_1 - E_2$, and let $C$ be the line through the two points.  There's an exact sequence $0 \to \mathcal O_X(kD-C) \to \mathcal O_X(kD) \to \mathcal O_C(kD \vert_C) \to 0$.  We have $h^2(X,kD-C) = 0$ for positive $k$ by Serre duality, so we get $h^1(X,kD) \geq h^1(C,kD\vert_C)$.  If $k \geq 2$ then $kD\vert_C$ has degree $\leq -2$ and so the guy on the right is positive.  This means $h^1(X,kD) > 0$ for any $k \geq 2$.
In the two-dimensional case this is somewhat tied up with the SHGH conjecture; I lifted this argument from "Variations on Nagata's Conjecture" by Ciliberto, Harbourne, Miranda, Ro\'e. Of course if you pick D to have some kind of positivity, you have a better chance, as discussed in another answer.
A: I expect that the answer depends on $d$, and for $d$ sufficiently small, the answer should be no. 
Take $S\subset \mathbb{P}^2$ to be the complete intersection of two forms $f,g$ of degree $a$, with $a$ sufficiently large. Let $I$ be the ideal generated by $f,g$.
Then the $km$-fold symmetric product $I^{(km)}$ of $I$ is generated by degree $km$-monomials in $f$ and $g$. The Castelnouvo-Mumford regularity of this latter is ideal is bigger than $kma$.
Since $I^{(km)}$ is the ideal of a zerodimensional scheme we obtain that the Hilbert function and Hilbert polynomial differ in every degree less than $kma$.
If you now sheafify you will find (after a small argument) that $h^1(\mathcal{F_k})>0$ holds for any $k>0$ if $d<ma$. I expect that you will get $h^1(X,\mathcal{O}_X(kD))>0$ from this.
A: It seems to me that you are looking for a kind of regularity result. By Remark $1.8.44$ in Lasarsfeld, Positivity in algebraic geometry 1, you have that if $X\subset\mathbb{P}^n$ is a smooth variety of codimension $c$ defined scheme-theoretically by polynomials of degrees $d_1\geq d_2\geq ...\geq d_m$. Then 
$$H^i(\mathbb{P}^n,\mathcal{I}^a(b)) = 0, \: for \: i>0, \: and \: b\geq ad_1+d_2+...+d_c-n.$$
Now, take $n = 3$ and $s = 2$. Then $S$ is a complete intersection of hypersurfaces of degrees $d_1 = 2$, $d_2 = 1$, $d_3 = 1$, and $4k \geq 4k+1+1-3 = 4k-1$ yields 
$$H^i(\mathbb{P}^3,\mathcal{I}^{2k}(4k)) = 0, \: for \: i>0.$$
These are the higher cohomology groups of the anti-canonical divisor. On the other hand if you take $s = 3$ you need four hypersurfaces of degrees $d_1 = d_2 = d_3 = 2$ and $d_4=1$. Then $4k<4k+2+2-3 = 4k+1$. Therefore this argument does not work anymore.
On the other hand , by Theorem 1.4.40 in Lazarsfeld, if $D$ is a nef divisor on a projective variety of dimension $n$, then for any coherent sheaf $\mathcal{F}$ on $X$ we have
$$h^i(X,\mathcal{F}(kD)) = O(k^{n-1}).$$
By Asymptotic Riemann Roch for a nef divisor $D$ one has
$$h^0(X,\mathcal{O}_X(kD)) = \frac{D^n}{n!}k^n+O(k^{n-1}).$$
In particular this works for $\mathbb{P}^3$ blown-up at $s\leq 7$ general points because, as you wrote, $-K_X$ is nef. Therefore, it is big being $(-K_X)^3 >0$.
This is to say that, if I interpreted in the right way your question, for this kind of issue it is better to use asymptotic theory that regularity results. 
