Edit. I edited the argument below to make it work in all characteristics. By SGA $7_{II}$ Exposé XVII, this requires working with a sufficiently general pencil of divisors in $\mathcal{O}_{\mathbb{P}^3}(e)|_S$ for $e\geq 2$ (as before, $e=1$ suffices if $d\geq 3$ and the characteristic is sufficiently large).
These kinds of arguments used to be "common knowledge", but times change, we use different methods now, etc. The statement is true for all smooth surfaces $S$ in $\mathbb{P}^3$ and every "very general" divisor $C\subset S$ in the linear system $\mathcal{O}_{\mathbb{P}^3}(e)|_S$ such that either $e\geq 2$ (all characteristics) or $e=1$ and $d\geq 3$ (sufficiently positive characteristics). In this case, there exists a Lefschetz pencil $\{C_p\}$ of divisors in the linear system $\mathcal{O}_{\mathbb{P}^3}(e)|_S$. A pencil of divisors is a Lefschetz pencil if (a) for all but finitely many $p$, $C_p$ is smooth, and (b) the finitely many singular $C_p$ are (geometrically) irreducible and reduced with a single ordinary double point. The existence of a Lefschetz pencil follows by SGA $7_{II}$, Exposé XVII by Nicholas Katz.
Let $\nu:\widetilde{S} \to S$ be the blowing up of the base locus of this pencil of divisors. Let $\pi:\widetilde{S}\to \Pi$ be the projection of $\widetilde{S}$ to $\Pi\cong \mathbb{P}^1$ such that the fiber of $\pi$ over $p\in \Pi$ equals the strict transform of the divisor $C_p \subset S$ in the pencil.
Denote by $\text{Pic}^\perp(S)$ the subgroup of $\text{Pic}(S)$ of classes $[\mathcal{L}]$ of invertible sheaves $\mathcal{L}$ on $S$ such that $(c_1(\mathcal{L}).c_1(\mathcal{O}_{\mathbb{P}^3}(1)|_S))_S$ equals $0$.
For every such $\mathcal{L}$ on $S$, denote by $F(\mathcal{L})$ the associated coherent sheaf on $\Pi$, $$F(\mathcal{L}) = R^1\pi_*(\omega_\pi\otimes_{\mathcal{O}_S} \nu^*\mathcal{L}^\vee).$$ Denote by $\eta$ the generic point of $\Pi$, and denote by $C_\eta \subset \widetilde{S}$ the generic fiber of $\pi$. Then, by cohomology and base change, $F(\mathcal{L})$ is a torsion sheaf unless $\nu^*\mathcal{L}|_{C_\eta}$ is isomorphic to $\mathcal{O}_{C_\eta}$, in which case $F(\mathcal{L})$ is a rank $1$ sheaf (a priori, not necessarily pure).
First consider the case that $F(\mathcal{L})$ is a rank $1$ sheaf. By cohomology and base change, there exists a dense open subscheme $U\subset \Pi$ such that $\nu^*\mathcal{L}|_{\pi^{-1}(U)}$ is isomorphic to the structure sheaf on $\pi^{-1}(U)$. Thus, there exists a rational section of $\nu^*\mathcal{L}$ whose support is contained in finitely many fibers of $\pi$. Since every fiber of $\pi$ is integral, it follows that $\nu^*\mathcal{L}$ is isomorphic to $\pi^*\mathcal{M}$ for some invertible sheaf $\mathcal{M}$ on $\Pi$. Since $\Pi$ is isomorphic to $\mathbb{P}^1$, $\nu^*\mathcal{L}\cong \pi^*\mathcal{O}(m)$ for some integer $m$. On the dense open subscheme $V\subset \widetilde{S}$ on which $\nu$ is an isomorphism, $\pi^*\mathcal{O}(1)$ is isomorphic to $\nu^* \mathcal{O}_{\mathbb{P}^3}(e)|_S$. Thus, by S2 extension, $\mathcal{L}$ is isomorphic to $\mathcal{O}_{\mathbb{P}^3}(me)|_S$. Since $[\mathcal{L}]$ is in $\text{Pic}^\perp(S)$, $me$ equals $0$. Thus $\mathcal{L}$ is isomorphic to $\mathcal{O}_S$.
Thus, for every nonzero element $[\mathcal{L}]$ in $\text{Pic}^\perp(S)$, the coherent sheaf $F(\mathcal{L})$ is torsion. Of course $\text{Pic}^\perp(S)\setminus\{0\}$ is a countable set by the theorem of Néron-Severi-Lang, i.e., the "Theorem of the Base", and the computation that $h^1(S,\mathcal{O}_S)$ is zero. Thus also the subset of $\Pi$, $$\Pi^\perp = \bigcup\{ \text{Support}(F(\mathcal{L})) : [\mathcal{L}] \in \text{Pic}^\perp(S)\setminus\{0\} \}, $$ is a countable set of closed points of $\Pi$. Assuming that the ground field is uncountable (or using the geometric generic point), for a "very general" point $p$ of $\Pi$, for every $[\mathcal{L}]$ in $\text{Pic}^\perp_(S)\setminus\{0\}$, $\mathcal{L}|_{C_p}$ is not isomorphic to $\mathcal{O}_{C_p}$.
Edit. It may be instructive to consider what goes wrong if $d$ equals $2$ and $e$ equals $1$. Then every pencil of hyperplane sections has two reducible fibers, $C_0 = A_0 \cup B_0$ and $C_\infty = A_\infty \cup B_\infty$. So in the argument above, we conclude that if $F(\mathcal{L})$ has rank $1$, then $\mathcal{L}$ is isomorphic to $\mathcal{O}_{\mathbb{P}^3}(m)|_S(a_0\underline{A}_0 + b_0\underline{B}_0+a_\infty\underline{A}_\infty+b_\infty\underline{B}_\infty)$ for integers $a_0$, $b_0$, $a_\infty$ and $b_\infty$. We can rewrite with $b_0=a_\infty=0$. Since $A_0\cup B_\infty$ is a hyperplane section, we can also rewrite with $b_\infty = 0$. Finally, since $\mathcal{L}$ is in $\text{Pic}^\perp(S)$, $a_0$ equals $-2m$. Thus, the kernel of the restriction map is generated by the class of $\mathcal{O}_{\mathbb{P}^3}(1)|_S(-2\underline{A}_0) \cong \mathcal{O}_S(\underline{B}_0-\underline{A}_0)$.
