You can solve the problem via integer linear programming as follows.  Let $N = \{1,\dots,n\}$ be the node set, and let $E = \{i \in N, j \in N: i < j\}$ be the set of node pairs.  For $(i,j)\in E$, let binary decision variable $x_{i,j}$ indicate whether edge $(i,j)$ appears in the graph.  For $i\in N$, let integer decision variable $d_i$ be the degree of node $i$.  For $(i,j)\in E$, let binary decision variables $u_{i,j}$ and $v_{i,j}$ indicate whether $d_i - d_j \ge k$ or $d_j - d_i \ge k$, respectively.
The problem is to maximize $$\sum_{(i,j) \in E} (u_{i,j} + v_{i,j}) \tag1$$
subject to 
\begin{align}
\sum_{(i,j) \in E} x_{i,j} + \sum_{(j,i) \in E} x_{j,i} &= d_i &&\text{for $i\in N$} \tag2\\
k - (d_i - d_j) &\le (k + n - 1) (1 - u_{i,j}) &&\text{for $(i,j)\in E$} \tag3\\
k - (d_j - d_i) &\le (k + n - 1) (1 - v_{i,j}) &&\text{for $(i,j)\in E$} \tag4\\
\end{align}
The objective $(1)$ maximizes the number of times that $|d_i-d_j| \ge k$.
Constraint $(2)$ enforces the definition of degree.
Constraint $(3)$ enforces the implication $u_{i,j} = 1 \implies d_i - d_j \ge k$.
Constraint $(4)$ enforces the implication $v_{i,j} = 1 \implies d_j - d_i \ge k$.

For $n \le 20$ and $\lfloor n/2 \rfloor \le k \le n-1$, the optimal objective value turns out to be $(k+1)(n-k-1)$.