Part of the order contained two 10uF electrolytic capacitors but at different ratings, one at 1000V and one at 630V (for what it's worth, the voltage I'm working with here is ~440V).
If you're sure both have 440V on them, you can use 600V for both, it's likely to be cheaper. I wonder why the original was rated at 1kV.
Would it matter if I were to use just two 1000V ones? What are any downsides in using a higher rated capacitor than what is called for?
Downside is price and bulk. Although modern caps are likely to be smaller than the ones you are replacing, so this shouldn't be a problem.
Now, to add to the other answers...
High-K ceramics like X7R etc are crap dielectrics if you consider the dC/dV, the capacitance varies a lot, it also varies with temperature. Also they are piezoelectric. Never use those in the signal path, for filtering, or for decoupling a high impedance node like a VREF (you'd get a piezo microphone).
So you may wonder why people use them so much. The reason is that they are very good for decoupling power supplies. Since the voltage is constant, dC/dV distortion doesn't matter. And ceramics have many advantages:
They are very cheap and give a high capacitance per volume. They withstand very high temperatures, so they can be surface-mounted directly on the board. This results in very low inductance, which is excellent for decoupling.
Note NP0 ceramics are another story, they are extremely linear and accurate.
EDIT
"High-K" means "High dielectric constant". \$ \kappa \$ is basically \$ \epsilon_r \$ Two plates with a bit of dielectric between them make a capacitor of value:
\$ \frac{Area * \epsilon_0 * \epsilon_r}{Thickness} \$
A material which is a good insulator can be thinner, so you get more capacitance per volume.
And a material with high dielectric constant \$ \kappa \$ or \$ \epsilon_r \$ also gives higher capacitance per volume.
Polypropylene has a dielectric constant of 2.2.
Barium Titanate (one of the High-K ceramics) has 7000. So, it packs a lot more capacitance into much less volume.
Plate thickness can get down to 0.5µm these days.
Drawback of these materials is that dielectric constant gets lower with higher electric field. A higher voltage rated X7R ceramic cap (say, 25V versus 6V) will have thicker plates, therefore electric field is lower, therefore its capacitance drops less at the same voltage (say, 3.3V for both caps).
Same if you buy a larger part (1206 is physically larger than 0603 for example) You get thicker plates, and possibly the manufacturer can use a less "extreme high K" material so capacitance drops less.
This explains the curves you posted. Note 1812, 1206 etc are package sizes.
This is off topic relative to your electrolytic caps, but since you asked ;)