Finding n farthest leaves in a tree
If you have a binary tree, you should be able to solve this using dynamic programming.
Let $A[v,j,k]$ denote the maximum possible value of the objective function
$$f'(N) = \sum_{x_1,x_2 \in N} \text{dist}(x_1,x_2) + k \sum_{x \in N} \text{dist}(v,x)$$
where $N$ ranges over all subsets of exactly $j$ leaves from among those that are descendants of $v$ (i.e., leaves of the subtree rooted at $v$).
If $v$ is a leaf, it is easy to compute $A[v,j,k]$ for all $j,k$.
If $v$ has one child $v'$, it is easy to compute $A[v,j,k]$ for all $j,k$ from $A[v',\cdot,\cdot]$.
So now suppose $v$ has two children $v',v''$.  Then we can work out a recursive equation for $A[v,j,k]$ in terms of values $A[w,\cdot,\cdot]$ where the $w$'s are descendants of $v$:
$$A[v,j,k] = \max A[v',j',k+j''] + A[v'',j'',k+j'] + 2 j' j'' + jk$$
where $j',j''$ range over all values such that $j'+j'' = j$, $0 \le j',j'' \le j$.  The intended meaning is that $j'$ counts the number of leaves in $N$ that are descendants of $v'$ and $j''$ counts the number of leaves in $N$ that are descendants of $v''$.  In other words, we split $N=N' \cup N''$ where $N'$ contains $j'$ leaves from the descendants of $v'$, and $N''$ contains $j''$ leaves from the descendants of $v''$; then (loosely speaking) we compute the maximum value of $f'(N)$ in terms of the maximum values of $f'(N')$ and $f'(N'')$.  The $2jj'$ term counts distances of the form $\text{dist}(x_1,x_2)$ where $x_1 \in N'$ and $x_2 \in N''$.  The $jk$ term accounts for the fact that the $j$ root-to-leaf paths all need to be extended by one edge (thank you @j_random_hacker).

If you have an arbitrary tree (not necessarily a binary tree), you can convert it to a binary tree as follows: whenever you have a node $v$ with $m$ children, create a little binary tree with $m$ leaves, then put $v$ at the root of that binary tree and paste the children of $v'$ in at its $m$ leaves.  Put a distance of 0 on all the edges of that new little binary tree except the top level.  Repeat recursively.
In this way you obtain a binary tree where every edge has a distance of either 0 or 1 on it, and the distance between two vertices $v,w$ is the sum of the distances on the edges in the path between $v$ and $w$.  Now you should be able to generalize the above algorithm to that case.  I'll let you handle the details.