What is the complexity of Hamming nearest neighbor to a subspace ...?
Your problem is known as the nearest codeword problem, and it is NP-hard to approximate. See for example lecture notes of Madhu Sudan. The way to make this problem an NP-problem is to ask whether the distance is at most a given distance. Regarding algorithms, I suggest taking a look at a paper of Alon, Panigrahy and Yekhanin, Deterministic Approximation Algorithms for the Nearest Codeword Problem.