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)$.

For small $n$ and $k$, 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)$.