Just noticed this. The problem has been already solved in two ways, but not the generalization suggested by H A Helfgott where the multiplier $2$ is replaced by an arbitrary constant (though the solution may be implicit in Alain Valette's answer). In fact, for any fixed $r$, $s$ and any $a_j$ ($1 \leq j \leq r$) and $m_k$ ($1 \leq k \leq s$) the graph of degree $2(r+s)$ on ${\bf Z} / p {\bf Z}$ obtained by joining every $x \bmod p$ to the $2(r+s)$ residues $x \pm a_j$ and $m_k^{\pm 1} x$ is not an expander as $p \rightarrow \infty$, no matter how the addends $a_j$ and multiplicands $m_k$ are chosen. This is basically what I gave as the "Exercise" at the end of my accepted answer to question MO.125251 on the analogous graphs on finite fields of $2^n$ elements. (The exercise concerned only $r=s=1$, but a comment noted that the same argument applies in for any fixed $r,s$).

To spell it out: Let $A = \sum_j A_j$ and $M = \sum_k M_k$ be the corresponding operators on ${\bf C}^p$, so that $A_j$ (respectively $M_k$) sends the unit vector $e_x$ to $e_{x+a_j} + e_{x-a_j}$ (resp. $e_{m_k x} + e_{m_k^{-1} x}$ The all-$1$ vector ${\bf 1}$ has eigenvalue $2(r+s)$ for $A+M$. We show that there is no spectral gap by finding a vector $v$ orthogonal to ${\bf 1}$ such that the Rayleigh quotient $\langle v, (A+M) v \rangle / \langle v, v \rangle$ is $2(r+s) - o(1)$ as $p \rightarrow \infty$, uniformly over all choices of $a_j$ and $m_k$. (The inner product is $\langle v, w \rangle = \frac1p \sum_{x \in {\bf Z}/p{\bf Z}} v_x \overline w_x$.)

Fix $N$. We'll construct $v$ such that $\langle v, (A+M) v \rangle / \langle v, v \rangle > 2(r+s) - 2s/N - o(1)$. For $u \in {\bf Z} / p{\bf Z}$ let $\chi_u$ be the character $x \mapsto e^{2\pi i u x/p}$ on ${\bf Z}/p{\bf Z}$, so that the $\chi_u$ form an orthonormal basis for ${\bf C}^p$. Set $$ v = \sum_c \chi_{m^c u_0} $$ for some nonzero $u_0 \in {\bf Z} / p{\bf Z}$ to be chosen later; here the sum extends over all integer vectors $c = (c_1,c_2,\ldots,c_s)$ with each $c_k \in [1,N]$, and $m^c := m_1^{c_1} m_2^{c_2} \cdots m_s^{c_s}$. Then $$ \langle v, M v \rangle \geq \frac{N-1}{N} 2s \langle v, v \rangle $$ (the inequality may be strict if there are small multiplicative relations among the $m_k$). Now each $\chi_u$ is an eigenvector for $A$ with eigenvalue $2\sum_{j=1}^r \cos (2 a_j u/p)$. We want to choose $u_0$ so that each of the $N^r s$ multiples $a_j m^c u_0$ is $o(p)$, so that $A \chi_{m^c u_0}$ has eigenvalue $2r-o(1)$ and $\langle v, A v \rangle = (2r-o(1)) \langle v, v \rangle$. By a standard pigeonhole argument such $u_0$ exists that makes each $a_j m^c u_0 / p$ within $O(p^{-1/N^r s})$ of an integer, uniformly over choices of $a_j$ and $m_k$. This gives the desired estimate as $p \rightarrow \infty$. Since $N$ can be taken arbitrarily large, we are done.

The special case $r=s=1$, $m_1=2$ is a bit easier: we can always take $u_0=1$ and obtain a bound $O(2^N/p)$ that decreases faster than $O(p^{-1/N})$.

Just noticed this. The problem has been already solved in two ways, but not the generalization suggested by H A Helfgott where the multiplier $2$ is replaced by an arbitrary constant (though the solution may be implicit in Alain Valette's answer). In fact, for any fixed $r$, $s$ and any $a_j$ ($1 \leq j \leq r$) and $m_k$ ($1 \leq k \leq s$) the graph of degree $2(r+s)$ on ${\bf Z} / p {\bf Z}$ obtained by joining every $x \bmod p$ to the $2(r+s)$ residues $x \pm a_j$ and $m_k^{\pm 1} x$ is not an expander as $p \rightarrow \infty$, no matter how the addends $a_j$ and multiplicands $m_k$ are chosen. This is basically what I gave as the "Exercise" at the end of my accepted answer to question MO.125251 on the analogous graphs on finite fields of $2^n$ elements. (The exercise concerned only $r=s=1$, but a comment noted that the same argument applies in for any fixed $r,s$).

To spell it out: Let $A = \sum_j A_j$ and $M = \sum_k M_k$ be the corresponding operators on ${\bf C}^p$, so that $A_j$ (respectively $M_k$) sends the unit vector $e_x$ to $e_{x+a_j} + e_{x-a_j}$ (resp. $e_{m_k x} + e_{m_k^{-1} x}$ The all-$1$ vector ${\bf 1}$ has eigenvalue $2(r+s)$ for $A+M$. We show that there is no spectral gap by finding a vector $v$ orthogonal to ${\bf 1}$ such that the Rayleigh quotient $\langle v, (A+M) v \rangle / \langle v, v \rangle$ is $2(r+s) - o(1)$ as $p \rightarrow \infty$, uniformly over all choices of $a_j$ and $m_k$. (The inner product is $\langle v, w \rangle = \frac1p \sum_{x \in {\bf Z}/p{\bf Z}} v_x \overline w_x$.)

Fix $N$. We'll construct $v$ such that $\langle v, (A+M) v \rangle / \langle v, v \rangle > 2(r+s) - 2s/N - o(1)$. For $u \in {\bf Z} / p{\bf Z}$ let $\chi_u$ be the character $x \mapsto e^{2\pi i u x/p}$ on ${\bf Z}/p{\bf Z}$, so that the $\chi_u$ form an orthonormal basis for ${\bf C}^p$. Set $$ v = \sum_c \chi_{m^c u_0} $$ for some nonzero $u_0 \in {\bf Z} / p{\bf Z}$ to be chosen later; here the sum extends over all integer vectors $c = (c_1,c_2,\ldots,c_s)$ with each $c_k \in [1,N]$, and $m^c := m_1^{c_1} m_2^{c_2} \cdots m_s^{c_s}$. Then $$ \langle v, M v \rangle \geq \frac{N-1}{N} 2s \langle v, v \rangle $$ (the inequality may be strict if there are small multiplicative relations among the $m_k$). Now each $\chi_u$ is an eigenvector for $A$ with eigenvalue $2\sum_{j=1}^r \cos (2 a_j u/p)$. We want to choose $u_0$ so that each of the $N^r s$ multiples $a_j m^c u_0$ is $o(p)$, so that $A \chi_{m^c u_0}$ has eigenvalue $2r-o(1)$ and $\langle v, A v \rangle = (2r-o(1)) \langle v, v \rangle$. By a standard pigeonhole argument such $u_0$ exists that makes each $a_j m^c u_0 / p$ within $O(p^{-1/N^r s})$ of an integer, uniformly over choices of $a_j$ and $m_k$. This gives the desired estimate as $p \rightarrow \infty$. Since $N$ can be taken arbitrarily large, we are done.

The special case $r=s=1$, $m_1=2$ is a bit easier: we can always take $u_0=1$ and obtain a bound $O(2^N/p)$ that decreases faster than $O(p^{-1/N})$.