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.