The two claims are true.
Proof for Claim 1 :
Let us prove by induction that
$$S_i\equiv 2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})\pmod M\tag1$$
where $s:=a-\sqrt{a^2-4},t=a+\sqrt{a^2-4}$.
$(1)$ holds for $i=0$ since
$$S_0\equiv P_{kb}(a)=2^{-kb}(s^{kb}+t^{kb})\pmod M$$
Supposing that $(1)$ holds for $i$ gives
$$\begin{align}S_{i+1}&=P_b(S_i)
\\\\&\equiv P_b(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))\pmod M
\\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-\sqrt{(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))^2-4}\bigg)^b
\\&\qquad\qquad+\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+\sqrt{(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))^2-4}\bigg)^b\bigg)
\\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-\sqrt{(2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}}))^2}\bigg)^b
\\&\qquad\qquad +\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+\sqrt{(2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}}))^2}\bigg)^b\bigg)
\\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}})\bigg)^b
\\&\qquad\qquad+\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}})\bigg)^b\bigg)
\\\\&=2^{-kb^{i+2}}(s^{kb^{i+2}}+t^{kb^{i+2}})\qquad\square\end{align}$$
From $(1)$, we get, using $2(a\pm\sqrt{a^2-4})=(\sqrt{a+2}\pm\sqrt{a-2})^2$,
$$\begin{align}S_{n-1}&\equiv 2^{-(M+c)}(s^{M+c}+t^{M+c})\pmod M
\\\\&=2^{-2M-2c}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2M+2c}
\\&\qquad\qquad\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2M+2c}\bigg)\tag2\end{align}$$
Here, we have, by the binomial theorem,
$$\begin{align}&(\sqrt{a+2}\pm\sqrt{a-2})^{M}
\\\\&=\sum_{k=0}^{M}\binom Mk(\sqrt{a+2})^{M-k}(\pm\sqrt{a-2})^k
\\\\&=\sqrt{a+2}\sum_{j=0}^{(M-1)/2}\binom{M}{2j}(a+2)^{(M-2j-1)/2}(a-2)^{j}
\\&\qquad\qquad \pm\sqrt{a-2}\sum_{j=1}^{(M+1)/2}\binom{M}{2j-1}(a+2)^{(M-2j+1)/2}(a-2)^{j-1}\end{align}$$
So, there are integers $C,D$ such that
$$(\sqrt{a+2}\pm\sqrt{a-2})^{M}=C\sqrt{a+2}\pm D\sqrt{a-2}$$
where
$$C=\sum_{j=0}^{(M-1)/2}\binom{M}{2j}(a+2)^{(M-2j-1)/2}(a-2)^{j}\equiv \left(\frac{a+2}{M}\right)\equiv 1\pmod M$$
and
$$D=\sum_{j=1}^{(M+1)/2}\binom{M}{2j-1}(a+2)^{(M-2j+1)/2}(a-2)^{j-1}\equiv \left(\frac{a-2}{M}\right)\equiv -1\pmod M$$
From $(2)$, we get
$$\begin{align}2^{2(M-1)}\cdot S_{n-1}&\equiv 2^{-2c-2}\left((\sqrt{a+2}-\sqrt{a-2})^{2M+2c}+(\sqrt{a+2}+\sqrt{a-2})^{2M+2c}\right)\pmod M
\\\\&=2^{-2c-2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c}(C\sqrt{a+2}- D\sqrt{a-2})^2
\\&\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2c}(C\sqrt{a+2}+ D\sqrt{a-2})^2\bigg)
\\\\&\equiv 2^{-2c-2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c}(\sqrt{a+2}+\sqrt{a-2})^2
\\&\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2c}(\sqrt{a+2}-\sqrt{a-2})^2\bigg)\pmod M
\\\\&=2^{-2c+2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c-2}+(\sqrt{a+2}+\sqrt{a-2})^{2c-2}\bigg)
\\\\&=2^{-(c-1)}(s^{c-1}+t^{c-1})
\\\\&=P_{c-1}(a)\end{align}$$
It follows from $2^{2(M-1)}\equiv 1\pmod M$ that
$$S_{n-1}\equiv P_{c-1}(a)\pmod M$$
Proof for Claim 2 :
From $(1)$, we get, similarly as above,
$$\begin{align}2^{2(N-1)}\cdot S_{n-1}&\equiv 2^{N+c-2}(s^{N-c}+t^{N-c})\pmod N
\\\\&=2^{2c-2}((\sqrt{s+2}-\sqrt{s-2})^{2N-2c}+(\sqrt{s+2}+\sqrt{s-2})^{2N-2c})
\\\\&=2^{2c-2}\bigg((\sqrt{s+2}-\sqrt{s-2})^{2N}\bigg(\frac{\sqrt{s+2}+\sqrt{s-2}}{4}\bigg)^{2c}
\\&\qquad\qquad +(\sqrt{s+2}+\sqrt{s-2})^{2N}\bigg(\frac{\sqrt{s+2}-\sqrt{s-2}}{4}\bigg)^{2c}\bigg)
\\\\&\equiv 2^{-2c-2}((\sqrt{s+2}-\sqrt{s-2})^2(\sqrt{s+2}+\sqrt{s-2})^{2c}
\\&\qquad\qquad +(\sqrt{s+2}+\sqrt{s-2})^2(\sqrt{s+2}-\sqrt{s-2})^{2c})\pmod N
\\\\&=2^{-2c+2}((\sqrt{s+2}+\sqrt{s-2})^{2c-2}+(\sqrt{s+2}-\sqrt{s-2})^{2c-2})
\\\\&=2^{-(c-1)}(s^{c-1}+t^{c-1})
\\\\&=P_{c-1}(a)\end{align}$$
It follows from $2^{2(N-1)}\equiv 1\pmod N$ that
$$S_{n-1}\equiv P_{c-1}(a)\pmod N$$
