We have computed the evolving ultraiolet-millimeter spectral energy distribution (SED) produced by protogalactic starbursts at high redshift, incorporating the chemical evolution of the interstellar medium in a consistent manner. Dust extinction is calculated in a novel way that is not based on empirical calibrations of extinction curves, but rather on the lifetime of molecular clouds which delays the emergence of each successive generation of stars at ultraviolet wavelengths by typically 15 Myr. The predicted rest-frame far-infrared-to-millimeter-wave emission includes the calculation of molecular emission-line luminosities ((CO)-C-12 and O-2 among other molecules) consistent with the evolving chemical abundances. Here we present details of this new model along with the results of comparing its predictions with several high-redshift observables, namely, the ultraviolet SEDs of Lyman limit galaxies, the high-redshift radio galaxies 4C 41.17 and 8C 1435, the SCUBA submillimeter survey of the Hubble Deep Field (HDF), and the SEDs of intermediate-redshift elliptical galaxies. With our new reddening method, we are able to fit the spectrum of the Lyman limit galaxy 1512-cB58, and we find an extinction of about 1.9 mag at 1600 Angstrom. This extinction applies to starbursts with spectral slope alpha in the range 0 less than or similar to alpha less than or similar to 1.5. The model also predicts that most Lyman limit galaxies should have a value of alpha inside that range, as is observed. The 850 mu m flux density of a typical Lyman limit galaxy is expected to be only similar or equal to 0.5 mJy, and therefore the optical counterparts of the most luminous submillimeter sources in the HDF (or any other currently feasible submillimeter survey) are unlikely to be Lyman break galaxies. The passive evolution of our starburst model is also compared with Keck observations of the reddest known elliptical galaxy at z similar to 1.5 and with the SED of a typical nearby elliptical galaxy. The SED of the high-redshift elliptical is nicely matched by the starburst model with an age of 4 Gyr and the SED of the nearby elliptical galaxy with an age of 13 Gyr.