Optimal combination, given pairwise costs
This is a generalization of independent set.  In particular, if all edge weights are either 0 or 1, then there's a solution to your problem with total sum 0 iff there is an independent set of size k.  It follows that your problem is NP-hard.

More usefully, your problem is equivalent to the maximum edge-weighted clique problem, which asks to find the $k$-clique that maximizes the sum of edge weights between clique vertices.  (Your versions asks to minimize the sum rather than maximize the sum, but if we negate the edge weights it becomes equivalent.)  Here's one example of a paper that studies that problem, and describes some experiments with different approaches to that problem:


Solving the maximum edge weight clique problem via unconstrained quadratic programming.  Bahram Alidaee, Fred Glover, Gary Kochenberger, Haibo Wang.  European Journal of Operational Research, vol 181, 2007.


A literature search seems to turn up other papers on the subject as well.  (See also https://stackoverflow.com/q/16625964/781723.)