In order to find the most extreme dust-hidden high-redshift galaxies, we select 196 extremely red objects in the Ks and IRAC bands (KIEROs, [Ks-4.5um](AB)>1.6) in the 0.06 deg^2 GOODS-N region. This selection avoids the Balmer breaks of galactic spectra at z<4 and picks up red galaxies with strong dust extinction. The photometric redshifts of KIEROs are between 1.5 and 5, with ~70% at z~2-4. KIEROs are very massive, with M*~10^10-10^12 Msun. They are optically faint and usually cannot be picked out by the Lyman break selection. On the other hand, the KIERO selection includes approximately half of the known millimeter and submillimeter galaxies in the GOODS-N. Stacking analyses in the radio, millimeter, and submillimeter all show that KIEROs are much more luminous than average 4.5um selected galaxies. Interestingly, the stacked fluxes for ACS-undetected KIEROs in these wavebands are 2.5-5 times larger than those for ACS-detected KIEROs. With the stacked radio fluxes and the local radio-FIR correlation, we derive mean infrared luminosities of 2-7x10^12 Lsun and mean star formation rates of 300-1200 Msun/yr for KIEROs with redshifts. We do not find evidence of a significant subpopulation of passive KIEROs. The large stellar masses and star formation rates imply that KIEROs are $z>2$ massive galaxies in rapid formation. Our results show that a large sample of dusty ultraluminous sources can be selected in this way and that a large fraction of high-redshift star formation is hidden by dust.