The existence of submillimeter-selected galaxies (SMGs) at redshifts z > 4 has recently been confirmed. Simultaneously using all the available data from UV to radio, we have modeled the spectral energy distributions of the six known spectroscopically confirmed SMGs at z > 4. We find that their star formation rates (average ~2500M sun yr-1), stellar (~3.6 × 1011 M sun) and dust (~6.7 × 108 M sun) masses, extinction (AV ~ 2.2 mag), and gas-to-dust ratios (~60) are within the ranges for 1.7 <z <3.6 SMGs. Our analysis suggests that infrared-to-radio luminosity ratios of SMGs do not change up to redshift ~5 and are lower by a factor of ~2.1 than the value corresponding to the local IR-radio correlation. However, we also find dissimilarities between z > 4 and lower-redshift SMGs. Those at z > 4 tend to be among the most star-forming, least massive, and hottest (~60 K) SMGs and exhibit the highest fraction of stellar mass formed in the ongoing starburst (~45%). This indicates that at z > 4 we see earlier stages of evolution of submillimeter-bright galaxies. Using the derived properties for z > 4 SMGs, we investigate the origin of dust at epochs less than 1.5 Gyr after the big bang. This is significant to our understanding of the evolution of the early universe. For three z > 4 SMGs, asymptotic giant branch stars could be the dominant dust producers. However, for the remaining three only supernovae (SNe) are efficient and fast enough to be responsible for dust production, though requiring a very high dust yield per SN (0.15-0.65 M sun). The required dust yields are lower if a top-heavy initial mass function or significant dust growth in the interstellar medium is assumed. We estimate lower limits of the contribution of SMGs to the cosmic star formation and stellar mass densities at z ~ 4-5 to be ~4% and ~1%, respectively.