What is the complexity of this submatrix selection problem?
EDIT: Added an answer meeting the unique-sum requirement.
Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique.
Proof. Here's the reduction.  First we describe the reduction to the problem without the requirement that the maximum is unique.
Fix a 3-CNF-SAT instance $\phi$.  Assume WLOG that $\phi$ has more clauses than variables (if not, just duplicate clauses to make it so).  Let $n$ be the number of clauses.
The reduction outputs a $kn\times kn$ matrix $M$, where $k=3$.  $M$ will be a 0/1 matrix, and will have an $n\times n$ submatrix of the desired form and having (at least) $n$ ones iff $\phi$ is satisfiable.
Create $M$ as follows. For each variable $x$ in $\phi$, create a window of three columns: a column $c(x)$ for the literal $x$, a column $c(\bar x)$ for the literal $\bar x$, and one dummy column whose entries are all zero (just so the window has the necessary three columns). Add additional windows of all-zero columns to bring the number of column-windows to the desired number $n$.
For each clause, say $C=\ell_1\vee \ell_2 \vee \ell_3$, create a window of three rows, one for each literal. Name the three rows, respectively, $r(C, \ell_1)$, $r(C, \ell_2)$, and $r(C, \ell_3)$.  In each row, make just one entry 1: for row $r(C, \ell_1)$ the entry in column $c(\ell_1)$, for row $r(C, \ell_2)$ the entry in column $c(\ell_2)$, and for row $r(C, \ell_3)$ the entry in column $c(\ell_3)$.  Make all other entries zero.
This completes the reduction.  To finish we observe that there will be a submatrix of the desired form (with a row in each row-window and a column in each column-window) having (at least) $n$ ones if and only if $\phi$ is satisfiable.
First, suppose that $\phi$ has a satisfying assignment $A$.  Choose the submatrix of $M$ as follows.  Use the columns corresponding to literals that $A$ makes true (one for each variable), and one (all-zero) column from each padding column-window.  For each clause $C$, choose a literal $\ell_i$ in $C$ that $A$ makes true, and choose the row $r(C, \ell_i)$ in $C$'s row-window.  This defines the $n\times n$ submatrix.  Each of its rows has a 1, so the total number of 1's in the submatrix is $n$.
Conversely, suppose that $M$ has a submatrix $M'$ of the desired form with at least $n$ ones.  For each variable $x$, $M'$ uses either the column for the literal $x$, the column for the literal $\bar x$, or the dummy column in $x$'s column-window.  If $M'$ uses one of the two literal columns, assign $x$ the value that makes the literal true.  Otherwise assign $x$ arbitrarily.  This defines the assignment.
To see that it must be a satisfying assignment, recall that the submatrix has $n$ rows, and each row of $M$ has at most one 1, so reach row of the submatrix $M'$ must have exactly one 1.   By the construction of the row-windows in $M$, then, for each clause $C=\ell_1\vee \ell_2 \vee \ell_3$, there is a row $r(C, \ell_i)$ in the submatrix that has a 1, necessarily in the entry for row $\ell_i$ (as this is the only 1 entry in that row).  So column $\ell_i$ must be in the submatrix, so the assignment must make $\ell_i$ true.
EDIT: added the part below to handle the unique-sum requirement.
Hence, the reduction is correct.  Finally, to reduce 3CNF-SAT to the problem when the maximum is required to be unique, modify the previous reduction to output the matrix $M^*$ obtained from $M$ by adding a small perturbation to each entry, specifically, such that
$$M^*_{ij} = M_{ij} + \epsilon_{ij} \text{ where } \epsilon_{ij}=1/2^{nki + j+1}.$$
Because $M$ is a 0/1 matrix, the sum of the values in any sub matrix of $M$ is an integer. Also, for any sub matrix $M'$ of $M^*$, the sum of the perturbations $\sum_{ij\in M'} \epsilon_{ij}$ is less than 1 and is unique (as it uniquely identifies the set of indices of entries in $M'$).  It follows that the valid submatrix of $M^*$ with maximum sum is unique, and has sum at least $n$ iff the given 3-CNF-SAT instance $\phi$ is satisfiable.
(And note that the size of the encoding of $M^*$ is still polynomial in the size of $\phi$.)
$~~\Box$
Exhaustive search takes time polynomial in $k^n$, which is polynomial in the input size in the case that $n$ is constant (but $k$ grows).  So that case (fixed $n$) has a poly-time algorithm.
One could ask further about, say, hardness of approximation.  The above reduction can be done from MAX-3SAT to show that the problem has no PTAS.  But to me it looks like the problem generalizes a variant of Bipartite Densest Subgraph, so may be even harder to approximate.  (This assumes the matrix has non-negative entries.  If negative entries are allowed, it's easy to extend the above reduction so that the optimal value is 1 iff $\phi$ is satisfiable, and zero or negative otherwise, so approximating within any factor is NP-hard).