We report Plateau de Bure Interferometer (PdBI) 1.1 mm continuum imaging towards two extremely red H-[4.5]>4 (AB) galaxies at z>3, which we have previously discovered making use of Spitzer SEDS and Hubble Space Telescope CANDELS ultra-deep images of the Ultra Deep Survey field. One of our objects is detected on the PdBI map with a 4.3 sigma significance, corresponding to Snu(1.1mm)=(0.78 +/- 0.18) mJy. By combining this detection with the Spitzer 8 and 24 micron photometry for this source, and SCUBA2 flux density upper limits, we infer that this galaxy is a composite active galactic nucleus/star-forming system. The infrared (IR)-derived star formation rate is SFR~(200 +/- 100) Msun/yr, which implies that this galaxy is a higher-redshift analogue of the ordinary ultra-luminous infrared galaxies (ULIRGs) more commonly found at z~2-3. In the field of the other target, we find a tentative 3.1 sigma detection on the PdBI 1.1 mm map, but 3.7 arcsec away of our target position, so it likely corresponds to a different object. In spite of the lower significance, the PdBI detection is supported by a close SCUBA2 3.3 sigma detection. No counterpart is found on either the deep SEDS or CANDELS maps, so, if real, the PdBI source could be similar in nature to the sub-millimetre source GN10. We conclude that the analysis of ultra-deep near- and mid-IR images offers an efficient, alternative route to discover new sites of powerful star formation activity at high redshifts.