[EDIT: as OP confirm that they need the Frobenius norm, this should be a complete solution for that case]

Since that norm is orthogonally invariant, 
$$
\|A - A'\| = \|P^T(A-A')\| = \|P^TA - DP^TA\| = \|(I-D)P^TA\|,
$$
so essentially the question becomes "you are allowed to zero out $n$ rows of $B= P^TA$; which choice leaves you with the minimum norm"? This looks like a simpler reformulation.

If the norm is the Frobenius norm, then the answer is choosing 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.