Not a full answer (but maybe need to fill computational details):
If I am not mistaken, you are using the group law of a conic $C$ to iterate a point $p_0$ by multiplication by $b$. In fact, $S_{n-2}$ is the $x$ coordinate of the point $b^{n-2}(kp_0)$ in $C$ of order $4$, therefore, $S_{n-1}$  of a point of order $2$ and finally $S_n$ for the $x$ coordinate of the identity of $C$. These $x$ coordinates are $0,-1,1$. If you find such a sequence (which corresponds to the iteration of a fixed point $kp_0$ by multiplication by $b$) then it means that $C(\mathbb{Z}/N)\cong \mathbb{Z}/(N+1)\mathbb{Z}=\mathbb{Z}/kb^n\mathbb{Z}$. Therefore prime. Your restriction $k<2^n$ I think can be $k<b^n$. I did not have time to calculate $C$ but it should be something doable.