Extreme high-frequency peaked BL Lac objects (EHBLs) are blazars which exhibit extremely energetic synchrotron emission. They also feature non-thermal gamma-ray emission whose peak lies in the very high-energy (VHE, E > 100 GeV) range, and in some sources exceeds 1TeV: this is the case of hard-TeV EHBLs such as 1ES 0229+200. With the aim of increasing the EHBL population, ten targets were observed with the MAGIC telescopes from 2010 to 2017, for a total of 262 h of good quality data. The data were complemented by coordinated Swift observations. The X-ray data analysis confirms that all the sources but two are EHBLs. The sources show only a modest variability and a harder-when-brighter behavior, typical for this class of objects. At VHE gamma rays, three new sources were detected and a hint of signal was found for another new source. In each case the intrinsic spectrum is compatible with the hypothesis of a hard-TeV nature of these EHBLs. The broadband spectral energy distributions (SEDs) of all sources are built and modeled in the framework of a single-zone purely leptonic model. The VHE gamma-ray detected sources were also interpreted with a spine-layer and a proton synchrotron models. The three models provide a good description of the SEDs. However, the resulting parameters differ substantially in the three scenarios, in particular the magnetization parameter. This work presents a first mini-catalog of VHE gamma-ray and multi-wavelength observations of EHBLs.