Runaway stars form bow shocks by ploughing through the interstellar medium at supersonic speeds and are promising sources of non-thermal emission of photons. One of these objects has been found to emit non-thermal radiation in the radio band. This triggered the development of theoretical models predicting non-thermal photons from radio up to very-high-energy (VHE, E $geq 0.1$TeV) gamma rays. Subsequently, one bow shock was also detected in X-ray observations. However, the data did not allow discrimination between a hot thermal and a non-thermal origin. Further observations of different candidates at X-ray energies showed no evidence for emission at the position of the bow shocks either. A systematic search in the textit{Fermi}-LAT energy regime resulted in flux upper limits for 27 candidates listed in the E-BOSS catalogue. Here we perform the first systematic search for VHE gamma-ray emission from bow shocks of runaway stars. Using all available archival H.E.S.S. data we search for very-high-energy gamma-ray emission at the positions of bow shock candidates listed in the second E-BOSS catalogue release. Out of the 73 bow shock candidates in this catalogue, 32 have been observed with H.E.S.S. None of the observed 32 bow shock candidates in this population study show significant emission in the H.E.S.S. energy range. Therefore, flux upper limits are calculated in five energy bins and the fraction of the kinetic wind power that is converted into VHE gamma rays is constrained. Emission from stellar bow shocks is not detected in the energy range between 0.14 and 18 TeV. The resulting upper limits constrain the level of VHE gamma-ray emission from these objects down to 0.1-1 % of the kinetic wind energy.