Ah, I see where the confusion is.
Yes, both plates already have both protons and electrons in them. In fact, almost all matter does, since protons and electrons are two of the fundamental building blocks of atoms.
When you have a fresh, uncharged capacitor, each plate has a relatively balanced ratio of electrons to protons, meaning that its charge is neutral.
Once you connect the capacitor to a power supply, a bunch of electrons are sucked out of the atoms in the plate connected to the positive power supply. At the same time, a bunch of electrons are pushed into the plate connected to the negative power supply.
The plate that ends up with much more electrons than protons is negatively charged, while the one with much fewer electrons than protons is positively charged.