Finding top k which are the most different from each other
Your problem is NP-hard, when $k$ is part of the input.  Let $G=(V,E)$ be an undirected graph.  If we set all the scores to zero and $\text{var}(u,v)$ to 1 if $(u,v) \in E$ and 0 otherwise, your problem is equivalent to asking whether $G$ contains a clique of size $k$.  This is a NP-hard problem.

If we set all the scores to zero and allow the variety values to be arbitrary, your problem is equivalent to the maximum edge-weighted clique problem (MEWCP), which has been studied in the literature.  For instance, you can use quadratic programming or ILP to look for solutions; these can take exponential time in the worst case, but might be useful in practice if the number of items is not too large.

Obviously, when we take into account that scores can be non-zero, the problem only gets harder.  You might be able to adapt methods for MEWCP to your problem, or express your problem directly as an ILP or QP.