What is this matrix column-selection problem, and how hard is it to approximate?
After more thought, I found a simple approximation-preserving reduction from independent set, showing that this problem is hard to approximate better than $n^{0.5}$. Here it is.

Consider a graph $G=(V,E)$ with n vertices. Construct the following matrices, with columns indexing the vertices.


For each vertex $v$, construct a matrix with the top row containing a 1 in column v, and a 0 elsewhere. All remaining rows are filled with $-\infty$.
For each edge $e=(u,v) \in E$, construct a matrix with the first row with $-\infty$ at $u$ and $0$ elsewhere, and the second row with $-\infty$ at $v$ and $0$ elsewhere. All remaining rows are filled with $-\infty$.


The matrices corresponding to edges penalize choosing two adjacent vertices in the graph by $-\infty$, essentially enforcing that the selected set of columns is an independent set of vertices. The matrices corresponding to vertices add one to the objective value for each column selected (i.e. for each vertex included in the independent set). Consequently, $val(S)$ is $-\infty$ for all non-independent sets S, and |S| for all independent sets S. 

This shows that the maximum of val(S) is as hard to approximate as the maximum cardinality of an independent set, as needed.