Okay, it turns out in retrospect that the problem is trivial. The answer is "no": such a bound does not hold in general.
A simple counterexample is yielded by taking A=1 (so that we effectively deal with ℂB ⊗ ℂC throughout), B=C=2, and taking
P = ½ ψψ* where ψ = e1 ⊗ e2 − e2 ⊗ e1
for standard basis vectors ej for ℂ2. Note that P is the projector onto the antisymmetric subspace of ℂB ⊗ ℂC. The map M may then be re-presented as
M(ρ) = ½ ρ + ½ UρU* where U = 1ℂB ⊗ 1ℂC − 2P.
The operator U is unitary, and has the effect of 'swapping' the two spaces B and C; that is, for all tensor products α ⊗ β , we have U(α ⊗ β) = β ⊗ α . We may then construct a state an operator ρ for which the desired bound does not hold, by taking a tensor product of a state an operator with low 2-norm with one of high 2-norm, e.g.
ρ = 1ℂB ⊗ e1e1*.
We then have trC(ρ) = 1ℂB , which has a 2-norm of $\sqrt 2$ ; and trC(UρU*) = 2 e1e1*, which has a 2-norm of $2$. By the convexity of the 2-norm, we may then show that || trC( M(ρ) ) ||2 > || trC(ρ) ||2 for this choice of P and ρ. A similar construction can be made for any B=C>1, and letting P be the projector onto the antisymmetric space of 1ℂB ⊗ 1 ℂC .
I'm interested now in what upper bounds may be obtained for || trC( M(ρ) ) ||2 − || trC(ρ) ||2 , or related quantities, in the case that P is a rank-1 projector on ℂB ⊗ ℂC . If anyone can show such an interesting such bound, I may 'accept' it; but for the meantime, this answers my original question.