Let $|D|$ be the linear system of degree $d$ hypersurfaces in $\mathbb{P}^n$ having multiplicity at least $m$ at $s$ general points. 


Then $|kD|$ is the linear system of degree $kd$ hypersurfaces in $\mathbb{P}^n$ having multiplicity at least $km$ at $s$ general points.


The expected number of conditions imposed by the $s$ points of multiplicity $km$ is then 
$$s\binom{km-1+n}{n}.$$ 
Some of these conditions may be linearly dependent. Then the actual number of conditions is 
$$s\binom{km-1+n}{n}-P(k) = s\frac{(km+n-1)\cdot ... \cdot km}{n!}-P(k) = \frac{sm^n}{n!}k^n + Q(k)-P(k)$$
where $P(k)$ is a polynomial in $k$, and $Q(k) = s\binom{km-1+n}{n}-\frac{sm^n}{n!}k^n$. In particular, $\deg(Q) = n-1$. 


Under which hypothesis may we conclude that $\deg(P)\leq n-1$? For instance, would it be enough to know that the linear system $|D|$ induces a birational map $\mathbb{P}^n\dashrightarrow X$?



Number of conditions imposed by fat points to a linear system
In general your polynomial $P(k)$ has degree $n$ as soon as there is a positive dimensional subscheme in the base locus of the linear system. Consider for instance the case $n=3$, $s = 2$, $m=2$, $d = 3$. Then the line through the two base points is in contained in the base locus of the linear system with multiplicity $1$. 


The rational map induced by this linear system is the projection of a Veronese $3$-fold $V$ in the $\mathbb{P}^{19}$ parametrizing cubics of $\mathbb{P}^3$ from the span of two general tangent spaces of $V$. Therefore, such a map is birational.


Now you can compute that two general points of multiplicity $2k$ impose 
$$2\binom{2k+3-1}{3}-\binom{k+3-2}{3}$$ 
conditions at the surfaces of degree $3k$ in $\mathbb{P}^3$. The binomial coefficient $\binom{k+3-2}{3}$ gives the contribution of the base line.


Therefore, in your notations we have 
$$\frac{2\cdot 8}{3!}k^3+Q(k)-P(k)$$
conditions, where $Q(k)= \frac{2}{3!}(12k^2+4k)$, and
$$P(k) = \frac{1}{3!}(k^3-k)$$
which is still a polynomial of degree three.


