I think we can do better. I will describe different strategies where the probability that $d_i > d_j$ depends only on $i-j$. Then by choosing a weighted average, we will give a lower bound for this probability greater than $1/2$, despite the fact that the length of the sequence is around $n^2$.
 
First, if $k \leq mn-m+1$, then we take $d_i = \lceil \frac{i+e}{m} \rceil$ for a random $e \in [0,\dots, m-1]$. Then if $j>i$, the probability that $d_j>d_i$ is $\min ( \frac{j-i}{m},1)$.

To complement it, we want a sequence where the probability that $d_j>d_i$ is close to $1$ for $j-i$ small. We can do the first part by setting $d_i = i+e$ mod $n$ for again a random $n$. However, it declines to $0$ for $j-i$ large, so the best we can get by averaging is $1/2$.

We will do better using more randomization to change the rate of growth. Let $\alpha$ be a random real number in $[1,2]$ and $\beta$ a random real number in $[0,n]$. Define $d_i = \lfloor \alpha i + \beta \rfloor$ mod $n$.

$$f ( \alpha (j-i) \mod n)$$

where $f(x)= (1-1/n) x$ for $x \in [0,1]$ and $1- x/n$ for $x \in [1,n]$.

So the relevant probability is:

$$ \int_1^2 f ( \alpha (j-i) \mod n)) d \alpha$$

For $(j-i)<n/2$, $\alpha(j-i)$ is never in the interval $[0,1]$ modulo $n$, and for $(j-i)>n/2$, the probability that it is in that interval is $O(1/n)$, so with $O(1/n)$ we may replace $f(x)$ by the simpler function defined using the fractional part, $1- \operatorname{frac}\left(\frac{x}{n} \right)$.

$$ \int_1^2 \left( 1- \operatorname{frac}\left(\frac{\alpha (j-i)}{n} \right) \right) d \alpha$$

Using the trivial bound $ \operatorname{frac}(x) \leq x$, this is $\geq 1 - \frac{3}{2}(j-i)$.  

It is also easy to see that this is always at least $1/4$. The worst case must occur when $(j-i)$ is less than $n$, because adding $n$ to $j-i$ sends the integral closer to $1/2$. Then in the intervals $[0,n/2]$ and $[n/2,n]$ the integral is given by a rational function whose minimum can be computed.

So ignoring $O(1/n)$ terms, we have another strategy where the probability that $d_j-d_i$ is at least $\max( 1- \frac{3}{2} \frac{j-i}{n}, 1/4)$.

Setting $m=n/2$, and taking the linear combination of $3/7$ times the first strategy and $4/7$ times the second, we get a probability of at least $4/7$, with $k$ around $n^2$.

This is a proof of concept demonstrating that $O(n^{1/p})$ is not best possible. I'm sure this can be optimized much further.