The Most Massive Galaxies at 3.0<z<4.0 in the NEWFIRM Medium-Band Survey: Properties and Improved Constraints on the Stellar Mass Function

[Abridged] We use the NEWFIRM Medium-Band Survey (NMBS) to characterize the properties of a mass-complete sample of 14 galaxies at 3.0<z<4.0 with M_star>2.5x10^11 Msun, and to derive more accurate measurements of the high-mass end of the stellar mass function (SMF) of galaxies at z=3.5, with significantly reduced contributions from photometric redshift errors and cosmic variance to the total error budget of the SMF. The typical very massive galaxy at z=3.5 is red and faint in the observer's optical, with median r=26.1, and rest-frame U-V=1.6. About 60% of the sample have optical colors satisfying either the U- or the B-dropout color criteria, although ~50% of these galaxies have r>25.5. About 30% of the sample has SFRs from SED modeling consistent with zero. However, >80% of the sample is detected at 24 micron, with total infrared luminosities in the range (0.5-4.0)x10^13 Lsun. This implies the presence of either dust-enshrouded starburst activity (with SFRs of 600-4300 Msun/yr) and/or highly-obscured active galactic nuclei (AGN). The contribution of galaxies with M_star>2.5x10^11 Msun to the total stellar mass budget at z=3.5 is ~8%. We find an evolution by a factor of 2-7 and 3-22 from z~5 and z~6, respectively, to z=3.5. The previously found disagreement at the high-mass end between observed and model-predicted SMFs is now significant at the 3sigma level. However, systematic uncertainties dominate the total error budget, with errors up to a factor of ~8 in the densities, bringing the observed SMF in marginal agreement with the predicted SMF. Additional systematic uncertainties on the high-mass end could be introduced by either 1) the intense star-formation and/or the very common AGN activities as inferred from the MIPS 24 micron detections, and/or 2) contamination by a significant population of massive, old, and dusty galaxies at z~2.6.