We find exponentially many exact quantum many-body scar states in a two-dimensional PXP model -- an effective model for a two-dimensional Rydberg atom array in the nearest-neighbor blockade regime. Such scar states are remarkably simple valence bond solids despite being at effectively infinite temperature, and thus strongly violate the eigenstate thermalization hypothesis. Given a particular boundary condition, such eigenstates have integer-valued energies. Moreover, certain charge-density-wave initial states give rise to strong oscillations in the Rydberg excitation density after a quantum quench and tower-like structures in their overlaps with eigenstates.