It doesn't get that ugly, if you're mainly concerned with large $n$ and $k$. Simple order-of-magnitude stuff indicates that something like $k>\alpha n$ is true (where $\alpha$ depends on $j$).
The inequality $\binom{n}{k}<\binom{n+j}{k-1}$ is exactly equivalent to $$1 < \frac{k}{n-k+1} \prod_{i=1}^j \frac{n+i}{n+i-k+1}.$$ Setting $k\approx \alpha n$ , and letting $n\to \infty$, this reduces to implies the inequality $$\frac{\alpha}{(1-\alpha)^{j+1}} > \geq 1.$$ This is easy to solve for $j$. To solve for $\alpha$ is rougher. Since $(1-m/j)^j\to e^{-m}$, one can see that for large $j$ we must have $\alpha>m/j$ (specifically, for each $m$, if $j$ is sufficiently large then $\alpha>m/j$).
It seems to me that $$\frac 1j < \alpha_j < \frac{\log j}{j}$$ for $j\ge 5$ follows from calculus. So here's the result: For Let $\alpha_j$ be the unique real solution to $\alpha=(1-\alpha)^{j+1}$ with $0<\alpha<1$. If $n,k$ are sufficiently large and $k>\alpha_j n$, then $\binom{n}{k}<\binom{n+j}{k-1}$. In particular, for each $j\ge 5$, if $n,k$ are sufficiently large with $k>\frac{\log(j)}{j} n $, then $\binom{n}{k}<\binom{n+j}{k-1}$.
