Solver for uniform matroid isomorphism
You can get a square-root speed-up with a time-space tradeoff if you are working in $\mathbb{F}_2$.
The matrix $M$ is a no-instance iff there exists a non-zero vector $v$ of Hamming weight $\le k$ (i.e., with at most $k$ non-zero coordinates) such that $Mv=0$.  This is equivalent to saying that there exist $t,u$ of Hamming weight $\le k/2$ such that $Mt=Mu$ (since then $M(t-u)=0$ and $t-u$ has Hamming weight $\le k$).
Now you can enumerate all such $t$ and store $Mt$ in a hashtable, and look for collisions (or, sort the values $Mt$ and look for repeats).  This requires approximately ${n \choose k/2}$ time and space, which is better than your brute-force method.  But again it only works over $\mathbb{F}_2$.
You can improve this a bit further as follows.  Randomly partition the $n$ coordinates into two groups of $n/2$ coordinates, and restrict $t$ to be non-zero only on the first group (its zero on the second group), and $u$ to be non-zero only on the second group (it is zero on the first group).  Then if such $v$ exists, with probability ${k \choose k/2}/2^k \approx 1/\sqrt{\pi k/2}$, there exist $t,u$ that satisfy this restriction.  So, enumerate all such $t$, store $Mt$ in a hashtable, and for each $u$, look up $Mu$ in the hashtable (or, merge a sorted list of $Mt$ values and a sorted list of $Mu$ values).  If you repeat $40 \sqrt{\pi k/2}$ times, with a different partition each time, then you'll have an overwhelming probability of finding a solution if one exists.
This requires $40 \sqrt{\pi k/2} {n/2 \choose k/2}$ time and space, which is better than the above.
It's possible you might be able to apply other algorithms for finding a low-weight codeword in a linear code to this problem, if you are working in $\mathbb{F}_2$.
If you are working over $\mathbb{F}_p$ with $p&gt;2$, then you can still do this method, and the running time will be something like $40 \sqrt{\pi k/2} {n/2 \choose k/2} (p-1)^{k/2}$ time and space.  We can compare this to the brute-force approach of enumerating all subsets of $k$ of the columns, then using Gaussian elimination to compute its rank; that will have running time ${n \choose k} k^3$.  The brute-force approach is better when $n/k \ll p$, and my approach is better when $n/k \gg p$.