5.C.

As shown in Figure 2, it is easy to see that the circle $C_{3}: x^{2}+(y-5)^{2}=4$ is symmetric to the circle $C_{1}$:
$$\begin{array}{l} (x-4)^{2}+ \\ (y-1)^{2}=4 \text { with respect to the line } y=x+1. \end{array}$$

Therefore, for any point $M$ on $C_{1}$, there exists a point $M^{\prime}$ on circle $C_{3}$ such that $|P M| = |P M^{\prime}|$. Thus, we only need to find the maximum value of $|P M^{\prime}| - |P N|$.
Notice that $|P M^{\prime}| - |P N| \leq |M^{\prime} N| \leq 4 + 2 = 6$. When the points are $P(0,1)$, $M^{\prime}(0,7)$, and $N(0,1)$, the equality holds.