With the recent discovery of a dozen dusty star-forming galaxies and around 30 quasars at z > 5 that are hyper-luminous in the infrared (μ L IR > 1013 L⊙, where μ is a lensing magnification factor), the possibility has opened up for SPICA, the proposed ESA M5 mid-/far-infrared mission, to extend its spectroscopic studies toward the epoch of reionisation and beyond. In this paper, we examine the feasibility and scientific potential of such observations with SPICA's far-infrared spectrometer SAFARI, which will probe a spectral range (35-230 μm) that will be unexplored by ALMA and JWST. Our simulations show that SAFARI is capable of delivering good-quality spectra for hyper-luminous infrared galaxies at z = 5 - 10, allowing us to sample spectral features in the rest-frame mid-infrared and to investigate a host of key scientific issues, such as the relative importance of star formation versus AGN, the hardness of the radiation field, the level of chemical enrichment, and the properties of the molecular gas. From a broader perspective, SAFARI offers the potential to open up a new frontier in the study of the early Universe, providing access to uniquely powerful spectral features for probing first-generation objects, such as the key cooling lines of low-metallicity or metal-free forming galaxies (fine-structure and H2 lines) and emission features of solid compounds freshly synthesised by Population III supernovae. Ultimately, SAFARI's ability to explore the high-redshift Universe will be determined by the availability of sufficiently bright targets (whether intrinsically luminous or gravitationally lensed). With its launch expected around 2030, SPICA is ideally positioned to take full advantage of upcoming wide-field surveys such as LSST, SKA, Euclid, and WFIRST, which are likely to provide extraordinary targets for SAFARI.