We confirm @YonatanN's conjecture:
Lemma 1. There is always an optimal solution $v'$ such that, for some $i'$, $|v_{i'}' - v_{i'}| = k$, while $v'_i = v_i$ for all $i\ne i'$.
@YonatanN's suggested algorithm (try all possible such solutions and choose the best) will give the following corollary:
Corollary 1. There is a polynomial-time algorithm for the problem in the post.
Proof of Lemma 1. Among optimal solutions, let $v'$ be one with a minimum number of offset indices, that is, $i$ such that $v'_i \ne v_i$.
Suppose for contradiction that $v'$ has at least two offset indices $h$ and $j$.
Case 1. First consider the case that $v'_h > v_h$ and $v'_j > v_j$.
Fix $\delta = d(h) - d(j)$, where
$$d(x) = |\{(x, i) \in E : v'_x > v'_i\}| - |\{(x, i) \in E : v'_x < v'_i\}|.$$
Imagine increasing $v'_h$ while decreasing $v'_j$ at unit rate by an arbitrarily small $\epsilon>0$.
This operation (for $\epsilon \le v'_j - v_j$) would preserve $\sum_{i} |v'_i - v_i|$, so the solution would remain feasible,
and it would increase the objective value at rate at least $\delta$.
We conclude by this thought experiment (and the optimality of $v'$) that $\delta \le 0$.
Now actually decrease $v'_h$ and increase $v'_j$, both at unit rate, until $v'_h = v_h$.
This increases the objective at rate at least $-\delta\ge 0$, and preserves feasibility,
so it yields another optimal solution with fewer offset indices (as $h$ is no longer offset),
contradicting the choice of $v'$.
(We use above that, as we continue to decrease $v'_h$ and increase $v'_j$, the rate of increase in the objective does not decrease. This is because all edges that contribute positively to the rate (e.g. $(i,h)$ with $v'_i > v'_h$) continue to do so, while edges that contribute negatively may start contributing positively.)
Case 2. Next consider the case that $v'_h > v_h$ and $v'_j < v_j$. Consider increasing $v'_h$ and $v'_j$ at unit rate by an arbitrarily small positive amount. This would preserve feasibility while increasing the objective at rate at least $\alpha = d(h) + d(j$). So $\alpha \le 0$.
Now decrease both $v'_h$ and $v'_j$ at unit rate until $v'_j = v_j$. This preserves feasibility while increasing the objective at rate at least $-\alpha \ge 0$, yielding another optimal solution with fewer offset indices, contradicting the choice of $v'$.
For each remaining case (e.g. $v'_h < v_h$ and $v'_j < v_j$), a symmetric argument shows that the case cannot happen. It follows that $v'$ has at most one offset index. Let $i'$ be that index, if it exists, and otherwise an arbitrary index. If $|v'_{i'} - v_{i'}| = k$, we are done, so assume $|v'_{i'} - v_{i'}| < k$.
Now decreasing $v'_{i'}$ would increase the objective at rate at least $d(i')$, so the optimality of $v'$ implies $d(i') \le 0$. So increase $v'_{i'}$ at unit rate until $|v'_{i'} - v_{i'}| = k$. This preserves feasibility, while increasing the objective at rate at least $-d(i') \ge 0$, giving the desired optimal solution. $~~~\Box$
