I adapt an argument from this blog post of mine, exploiting the $\ell^2$ boundedness of the discrete Hilbert transform (i.e. Hilbert's inequality), to obtain an exponential upper bound. I don't see any obvious way to improve this to a polynomial bound. The argument is inspired by a stability result of Hrushovski (based on de Finetti's theorem) which shows that some finite bound is possible, although it is not easy to extract a quantitative bound from Hrushovski's argument (and if one did, it would surely be worse than exponential); see Proposition 2.25 of that paper.
Suppose that ${\bf P}(d_j > d_i) \geq r$ for some $r>1/2$ and all $1 \le i < j \leq k$. Then of course $${\bf P}( d_j > d_i) - {\bf P}( d_j < d_i ) \geq 2r-1$$ for all $1 \le i < j \le k$. We expand this as $$ \sum_{1 \leq a < b \leq n} {\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b ) \geq 2r-1.$$ Multiply by the positive quantity $\frac{1}{j-i}$ and sum to conclude that $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i < j \leq k} \frac{1}{j-i} [{\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b )] \gg (2r-1) k \log k.$$ The LHS can be rearranged as $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} {\bf P}(d_j = b \wedge d_i = a ) $$ and rearranged further as $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a}.$$ By Hilbert's inequality, we have $$ \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll (\sum_{1 \leq j \leq k} 1_{d_j=b})^{1/2} (\sum_{1 \leq i \leq k} 1_{d_i=a})^{1/2}$$ and $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq j \leq k} 1_{d_j=b}, {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i \leq k} 1_{d_i=a} \ll k n $$ so by Cauchy-Schwarz $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll kn $$ and hence $$ kn \gg (2r-1) k \log k$$ leading to the exponential upper bound $$ k \ll \exp( O( \frac{n}{2r-1} ) ).$$