We present far-IR (57-196 mu) spectra of 21 protostars in the Orion molecular clouds, obtained with the Photodetector Array Camera and Spectrometer (PACS) onboard the Herschel Space observatory, as part of the Herschel Orion Protostar Survey (HOPS) program. We analyzed the CO emission lines (J_up = 14-46) in the PACS spectra, extracted within a projected distance of <= 2000 AU centered on the protostar. The total luminosity of the CO lines observed with PACS (L(CO)) is found to increase with increasing L_bol. The CO rotational temperature implied by the line ratios increases with J, and at least 3-4 rotational temperature components are required to fit the observed rotational diagram. The rotational temperature components are remarkably invariant between protostars and show no dependence on L_bol, T_bol or envelope density, implying that if the emitting gas is in LTE, the CO emission must arise in multiple temperature components that remain independent of L_bol over two orders of magnitudes. The observed CO emission can also be modeled as arising from a single temperature gas component or from a medium with a power-law temperature distribution; both of these require sub-thermally excited molecular gas at low densities (n(H_2) <= 10^6 cm^-3) and high temperatures (T >= 2000 K). Our results suggest that the contribution from PDRs along the envelope cavity walls is unlikely to be the dominant component of the CO emission observed with PACS. Instead, the "universality" of the rotational temperatures and the observed correlation between L(CO) and L_bol can most easily be explained if the observed CO emission originates in shock-heated, hot (T >= 2000 K), sub-thermally excited (n(H_2) <= 10^6 cm^-3) molecular gas. Post-shock gas at these densities is more likely to be found within the outflow cavities along the molecular outflow or along the cavity walls at radii >= several 100-1000 AU.