Wolfram Language (Mathematica), 37 bytes

-2 bytes thanks to @att.

EdgeList[GraphPower@##~EdgeDelete~#]&

Try it online!

Of course there is a built-in for graph powers.

APL(Dyalog Unicode), 41 39 bytes ^SBCS

-2 bytes since ~x∨~y ←→ x<y

{⍸(∨\i)∧m<i∨.∧⍣⍺⍨m←∨∘⍉⍨1@⍵⊢i←∘.=⍨⍳⌈⌿∊⍵}

Try it on APLgolf!

A dfn that takes k as its left argument and the edges of a graph \$G\$ as its right argument, and outputs a list of edges that are in \$G^k\$ but not in \$G\$. It assumes the vertices come in 1 indexed.

Details

{⍸(∨\i)∧~m∨~i∨.∧⍣⍺⍨m←∨∘⍉⍨1@⍵⊢i←∘.=⍨⍳⌈⌿∊⍵}
                                    ⌈⌿∊⍵     number of nodes
                             i←∘.=⍨⍳         adjacency matrix of self loops
                   m←∨∘⍉⍨1@⍵⊢                adjacency matrix of G
            i∨.∧⍣⍺⍨                          adjacency matrix of ⍺th power of G
        ~m∨~                                   without edges in G
  (∨\i)∧                                       without edges (i j) such that i < j
 ⍸                                           list of edges in the adjacency matrix

JavaScript (ES10), 140 bytes

Expects (a)(n), where the edge list a is in the format used in the challenge. Prints the new edges.

a=>n=>a.flatMap(b=>a[b]=b).map(p=>(g=(k,v)=>k&&a.map(([x,y])=>x-v&&y-v||g(k-1,x^=y^v,a[P=[p,x]]||a[[x,p]]||p-x&&console.log(a[P]=P))))(n,p))

Try it online!

Python 3, 101 bytes

f=lambda g,k:k and{v:k>0and f(g,1-k)[v]-g[v]-{v}or g[v].union(*map(f(g,1+k).get,g[v]))for v in g}or g

Try it online!

Takes input as a dictionary containing a set of edges for every vertex, and outputs in the same format.

Charcoal, 48 bytes

Ｆ⊖ηＦ⁺θυＦΦθ⁼¹Ｌ⁻λκ«≔⁺⁻κλ⁻λκζ≔⟦⌊ζ⌈ζ⟧ζ¿¬№⁺υθζ⊞υζ»⭆¹υ

Try it online! Link is to verbose version of code. Explanation:

Ｆ⊖η

Loop k-1 times.

Ｆ⁺θυ

Loop over all of the edges found so far. This is done because we're mutating the list of additional edges and we don't want to accidentally loop over an unseen edge.

ＦΦθ⁼¹Ｌ⁻λκ«

Loop over all of the original edges that share exactly one vertex with the current edge.

≔⁺⁻κλ⁻λκζ≔⟦⌊ζ⌈ζ⟧ζ

Calculate the new edge.

¿¬№⁺υθζ⊞υζ

If this edge is unseen then add it to the list of additional edges.

»⭆¹υ

Output the final list of additional edges.