We say that a player makes the move $(i, a_i)$ if he chooses the index $i$ and then the element $a_i$ of the $\{0, 1, \dots, 9\}$ in this move.

(1) If $p=2$ or $p=5$, then the first player simply chooses $(0, 0)$, which forces $10|M$, which guarantees he wins.

(2) So assume $p \notin \{2, 5\}$. Let the first player choose $(p-1, 0)$ in the first move. By Fermat's Little Theorem, $(10^{(p-1)/2})^2 = 10^{p-1} \equiv 1 \pmod p$, so $p|(10^{(p-1)/2})^2 - 1 = (10^{(p-1)/2} - 1)(10^{(p-1)/2} + 1)$. Since $p$ is prime, we are left with two cases:

(i) $p|10^{(p-1)/2} - 1$

In this case, for each move $(i, a_i)$ made by the second player, the first player immediately makes a move
$$(j, a_j) = \begin{cases} (i + \frac{p-1}{2}, a_i), & 0 \le i \le \frac{p-3}{2}; \\ (i - \frac{p-1}{2}, a_i), & \frac{p-1}{2} \le i \le p-2. \end{cases}$$

This makes the sum be divisible by $p$, thus wins the game. One can easily check that this move is always possible.

(ii) $p|10^{\frac{(p-1)}{2}} + 1$

In this case, for each move $(i, a_i)$ made by the second player, the first player immediately makes a move
$$(j, a_j) = \begin{cases} (i + \frac{p-1}{2}, 9 - a_i), & 0 \le i \le \frac{p-3}{2} \\ (i - \frac{p-1}{2}, 9 - a_i), & \frac{p-1}{2} \le i \le p-2. \end{cases}$$

In any case, we will have $10^j \equiv 10^i \pmod p$, and hence, $a_j 10^j + a_i 10^i \equiv (a_j + a_i) 10^i = 9 \times 10^i \pmod p$. Therefore, at the end of the game, $M$ would be congruent to
$$\sum_{i=0}^{(p-3)/2} 9 \times 10^i = 10^{\frac{(p-1)}{2}} - 1 \equiv 0 \pmod{p}.$$
This ensures that the first player wins. Again, one can easily check that this move is always possible.