We present a study of rest-frame UV-to-optical color distributions for z~4 galaxies based on the combination of deep HST/ACS+WFC3/IR data with Spitzer/IRAC imaging. In particular, we use new, ultra-deep data from the IRAC Ultradeep Field program (IUDF10). Our sample contains a total of ~2600 galaxies selected as B-dropout Lyman Break Galaxies (LBGs) in the HUDF and one of its deep parallel fields, the HUDF09-2, as well as GOODS-North and South. This sample is used to investigate the UV continuum slopes beta and Balmer break colors (J_125-[4.5]) as a function of rest-frame optical luminosity. The [4.5] filter is chosen to avoid potential contamination by strong rest-frame optical emission lines. We find that galaxies at M_z<-21.5 (roughly corresponding to L*[z~4]) are significantly redder than their lower luminosity counterparts. The UV continuum slopes and the J_125-[4.5] colors are well correlated. The most simple explanation for this correlation is that the dust reddening at these redshifts is better described by an SMC-like extinction curve, rather than the typically assumed Calzetti reddening. After correcting for dust, we find that the galaxy population shows mean stellar population ages in the range 10^8.5 to 10^9 yr, with a dispersion of ~0.5 dex, and only weak trends as a function of luminosity. In contrast to some results from the literature, we find that only a small fraction of galaxies shows Balmer break colors which are consistent with extremely young ages, younger than 100 Myr. Under the assumption of smooth star-formation histories, this fraction is only 12-19% for galaxies at M_z<-19.75. Our results are consistent with a gradual build-up of stars and dust in galaxies at z>4, with only a small fraction of stars being formed in short, intense bursts of star-formation.