Just a long comment.

I assume the norm is the operator norm (induced by the Euclidean 2-norm). Then it is orthogonally invariant and 
$$
\|A - A'\| = \|P^T(A-A')\| = \|DP^TA - P^TA\|,
$$
so essentially the question becomes "you are allowed to keep $n$ rows of $B= P^TA$; which choice gives you the largest 2-norm"? This looks like a simpler reformulation.

If the norm were the Frobenius norm, then clearly the answer would be keeping the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.