Approximately sorting integers by many criteria
I don't know if there is an efficient algorithm that will always produce the optimal solution.  I would suggest looking at heuristics that hopefully will often work well, even if they don't come with guarantees.  One plausible approach would be to use simulated annealing, or some other form of local search.  At any point, you can pick a pair of random indices $i,j$ and consider would happen to $r$ if you swap the items at those two locations; then the simulated annealing algorithms describes the conditions under which you apply that swap vs not.  Repeat until convergence.  There are no guarantees this will give the global optimum -- it get stuck in a local optimum -- but it could be worth a try.



If you are OK with maximizing $\sum_i r_i$ instead of maximizing $\sum_i r_i^2$, the following might work.  You might be able to reduce this to the assignment problem and then apply a standard algorithm for the assignment problem.  In particular, for each item $i$ and each rank $j \in \{0,1,2,\dots,n\}$ create an edge from item $i$ to rank $j$ whose cost is $\sum_k 6(j-R_k(i))^2/n(n^2-1)$.  Then, use an algorithm for the assignment problem to find an assignment that assigns a unique rank to each item.   The sum of the costs of the selected edges will be equal to $k-\sum_i r_i$, so minimizing the sum of the costs will maximize $\sum_i r_i$.  Assigning each item to a unique rank is equivalent to sorting the items; you just put the items in order of their rank.  The assignment problem ensures that no two items will receive the same rank, and every item will receive some rank.

I'm not sure if this works or not.  At one point I thought this would work; then at another point I thought it wouldn't work (but I can't remember why not); and now I'm thinking again that this should work, and give a polynomial-time algorithm to find the exact solution for maximizing $\sum_i r_i$.  As you can see, I've gotten myself totally mixed up here, so I don't trust my thought process.  Double-check all of my reasoning here before placing any reliance on it.  (Even if this doesn't give the optimal answer, it's also possible that it provides a useful initialization for simulated annealing.)