(This answer expands on Albert Hendriks' approach from the comments.)
First idea: let us turn the problem around.
As stated, we fix the number of covered edges, $k$, and minimize the maximum length of an uncovered path $d(k)$.
Instead, let us fix the maximum length of an uncovered path, $d$, and minimize the number of covered edges $k(d)$.
Suppose now we can calculate $k(d)$ in $O(n)$.
Then the original problem can be solved in $O(n \log n)$.
Indeed, note that both $d(k)$ and $k(d)$ are non-increasing functions.
To answer the question "what is $d(k_0)$?", we can find the minimum $d_0$ such that $k(d_0) \le k_0$.
And that can be done in $log (n)$ calculations of $k(d)$ by doing a binary search for the right $d$ with the obvious bounds of $[0, n-1]$.
What's left is to, given a fixed value $d$, calculate $k(d)$ in $O(n)$.
Second idea: we can select an arbitrary vertex as the root, run a depth-first search from the root, and make decisions about covering edges in depth-first search order.
Let us visit a vertex $v$ in our depth-first search.
We recursively visit all its children in any order.
After visiting child $u$, we assume that we have dealt with all uncovered paths longer than $d$ in $u$'s subtree.
We also know the length $\mathrm{dfs}(u) \le d$ of the longest uncovered path from $u$ to the vertices of its subtree.
The longest uncovered path from $v$ to the vertices of $u$'s subtree has an extra edge $v - u$, so its length is $r = \mathrm{dfs}(u) + 1$.
(I) Obviously, if $r > d$ (it can only be $d + 1$), we have to cover some edge on the long path we found.
Since the whole subtree of $u$ is already dealt with, it makes sense to cover an edge which is the closest to the complement of the subtree of $u$ in the whole tree, which is the edge $v - u$.
(II) But there's more to consider.
A path can go from the subtree of one of our children, via our vertex $v$, to the subtree of another child.
And if such path has length greater than $d$, we have to cover an edge on it.
To find such paths, for our vertex $v$, we store the maximum length of an uncovered path into a child's subtree we have so far.
Let this stored length be $s$, initially zero.
After each child $u$ we visit, check whether $r + s > d$.
If so, let us cover the edge to the longest of $r$ and $s$, so the new maximum length of an uncovered path becomes $s_{\textit{new}} = \min (s_{\textit{old}}, r)$.
If $r + s \le d$, we don't yet have to cover anything, and the new maximum length is $s_{\textit{new}} = \max (s_{\textit{old}}, r)$.
Note now that, with such implementation, case (I) is covered by case (II).
In particular, if we don't yet store a path in a child's subtree, the stored value just adds a length of $0$.
When we finish visiting all children of $v$, the stored value $s$ is the length of the longest remaining uncovered path from $v$ to the vertices of its subtree.
In particular, if $v$ is a leaf, the value $s$ remained zero.
We can now return this value as $\mathrm{dfs}(v)$.
The remaining question is, if we don't cover an edge using the algorithm above, could it have helped us later if we had in fact covered it?
The answer is no: such a cover could safely be moved at least one step closer to the root of the tree, without altering other covers.
In pseudocode, with a bit more low-level details than the explanation above.
Assume the vertices are numbered 0, 1, ..., n-1.
We select vertex 0 as the root (recall that the root can be arbitrary), and just call dfs (0, -1).
dfs (v, p): // v is current vertex, p is its parent
{s, w} := {0, -1} // maximum path of length s into child w's subtree
for u in adjacent[v]: // all neighbors of v...
if u != p: // ...except its parent, if it has one
r := dfs (u, v) + 1
if r + s > d: // we have to cover the longest...
if r > s:
cover (v, u)
else:
cover (v, w)
{s, w} := {r, u} // ...and possibly update to shortest
else:
if r > s:
{s, w} := {r, u} // here, update to longest
return s // length of the longest remaining path
As we can see, dfs (v, p) returns the length of the longest uncovered path from $v$ to the vertices of its subtree.
So, we set the value d (to the pseudocode, it acts as a global variable), run dfs, and track the number of covered edges as the total number of calls to the cover function.
The cover function may actually record the covered edges if need be, but at the very least, it increases the counter k by 1.
If the edges themselves are not needed, we can drop the variable w too, and leave only s from the tuple {s, w}.
For the original problem, do the above in a binary search over the possible values of d to get the full solution.
