I would add to Taka's answer, since the Choi-Effros paper is not widely available online, that the nontrivial parts of the proof are to show the "C$^*$-identity" $\|x\|^2=\|x^*x\|$, associativity, and to check the completeness of $P(A)$.
Indeed, the algebra $(P(A),+,\circ)$ is a $*$-algebra, normed with the norm inherited from $A$. For the C$^*$-identity, since $P$ is contractive we have
\[ \|x^*\circ x\|=\|P(x^*x)\|\leq\|x^*x\|=\|x\|^2. \]
On the other hand, since $P$ is cp and contractive, it satisfies the Schwarz inequality $P(x)^*P(x)\leq P(x^*x)$, and so, for any $x\in P(A)$,
\[ \|x^*\circ x\|=\|P(x^*x)\|\geq \|P(x)^*P(x)\|=\|x^*x\|=\|x\|^2. \]
Completeness follows from the fact that $P$ is a bounded projection. If $\{x_j\}$ is a Cauchy sequence in $P(A)$, then by the completeness of $A$ the sequence converges to some $x$ in $A$. As $P$ is bounded, $P(x_j)\to P(x)$; but $P(x_j)=x_j$ (since $P$ is a projection and $x_j\in P(A)$) and so $P(x)=x$, that is $x\in P(A)$. So $P(A)$ is closed.
For the associativity of the product, one needs to check that $P(aP(bc))=P(P(ab)c)$ for any $a,b,c\in A$. For this, since $P$ is selfadjoint, it is enough to show that $P(xP(a))=P(xa)$ for any $x\in P(A)$, $a\in A$. The trick that Choi-Effros use (in Paulsen's version here) is to apply the Schwarz inequality to the ccp map $P^{(2)}$ and the operator $y=\begin{bmatrix}x^*&a\\ 0&0\end{bmatrix}$: thus $P^{(2)}(y)^*P^{(2)}(y)\leq P^{(2)}(y^*y)$ reads
\[ \begin{bmatrix}xx^*&xP(a)\\ P(a^*)x^*&P(a^*)P(a) \end{bmatrix} \leq \begin{bmatrix}P(xx^*)&P(xa)\\P(a^*x^*)&P(a^*a)\end{bmatrix} \]
If we now apply $P^{(2)}$ to this inequality, since it preserves positivity, we get
\[ \begin{bmatrix} 0&P(xa)-P(xP(a))\\ P(a^*x^*-P(P(a^*)x^*))& P(a^*a)-P(P(a^*)P(a))\end{bmatrix} \geq0; \]
the 0 in the 1,1 entry forces the off-diagonal entries to be zero, so $P(xa)=P(xP(a))$.