We report the detection of CO(J = 2 → 1) emission from three massive dusty starburst galaxies at z > 5 through molecular line scans in the NSF's Karl G. Jansky Very Large Array (VLA) CO Luminosity Density at High Redshift (COLDz) survey. Redshifts for two of the sources, HDF 850.1 (z = 5.183) and AzTEC-3 (z = 5.298), were previously known. We revise a previous redshift estimate for the third source GN10 (z = 5.303), which we have independently confirmed through detections of CO J = 1 → 0, 5 → 4, 6 → 5, and [C II] 158 μm emission with the VLA and the NOrthern Extended Milllimeter Array. We find that two currently independently confirmed CO sources in COLDz are "optically dark", and that three of them are dust-obscured galaxies at z > 5. Given our survey area of ∼60 arcmin2, our results appear to imply a ∼6-55 times higher space density of such distant dusty systems within the first billion years after the Big Bang than previously thought. At least two of these z > 5 galaxies show star formation rate surface densities consistent with so-called "maximum" starbursts, but we find significant differences in CO excitation between them. This result may suggest that different fractions of the massive gas reservoirs are located in the dense, star-forming nuclear regions—consistent with the more extended sizes of the [C II] emission compared to the dust continuum and higher [C II]-to-far-infrared luminosity ratios in those galaxies with lower gas excitation. We thus find substantial variations in the conditions for star formation between z > 5 dusty starbursts, which typically have dust temperatures that are ∼57% ± 25% warmer than starbursts at z = 2-3 due to their enhanced star formation activity.