Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?
Once you know how to count  the number of such arrays, you can turn that into a procedure to generate a random such array, using ranking/unranking procedures.

Let's see how to count them.  Let $f(k,m,n)$ denote the number of such arrays.  Note that we have

$$f(k,m,n) = \sum_{x=0}^k f(k,m-x,n-1)$$

by enumerating all possibilities for $A[0]$.  So, this gives a dynamic programming algorithm to count the number of such arrays.

How does this lead to a way to generate a random array?  Well, in counting such arrays, we've implicitly established a bijection $\varphi$ from the set of such arrays to the set of integers $\{0,1,2,\dots,f(k,m,n)-1\}$.  So, we just need a way to compute $\varphi^{-1}$, and then we have a way to pick a random array: we pick a random number between $0$ and $f(k,m,n)-1$, then apply $\varphi^{-1}$ to obtain the corresponding array.

Now the recurrence above establishes such a bijection.  In particular, the arrays that start with $A[0]=0$ correspond to integers in the range $0 .. f(k,m,n-1)-1$, the arrays that start with $A[0]=1$ correspond to integers in the range $f(k,m,n-1)..f(k,m,n-1)+f(k,m-1,n-1)-1$, and so on.  So, given a random integer $y$, we find the smallest $x_0$ such that

$$y &lt; \sum_{x=0}^{x_0} f(k,m-x,n-1),$$

and then set $A[0]=x_0$ and continue recursively to fill in the rest of the array (replacing $y$ with $y' = y - \sum_{x=0}^{x_0-1} f(k,m-x,n-1)$ and using $y'$ to fill in the array $A[1..n-1]$).