The recently detected gamma-ray emission from Starburst galaxies is most commonly considered to be diffuse emission arising from strong interactions of accelerated cosmic rays. Mannheim et al. (2012), however, have argued that a population of individual pulsar-wind nebulae (PWNe) could be responsible for the detected TeV emission. Here we show that the Starburst environment plays a critical role in the TeV emission from Starburst PWNe, and perform the first detailed calculations for this scenario. Our approach is based on the measured star-formation rates in the Starburst nuclei of NGC 253 and M 82, assumed pulsar birth periods and a simple model for the injection of non-thermal particles. The two-zone model applied here takes into account the high far-infrared radiation field, and different densities and magnetic fields in the PWNe and the Starburst regions, as well as particle escape. We confirm that PWNe can make a significant contribution to the TeV fluxes, provided that the injection spectrum of particles is rather hard and that the average pulsar birth period is rather short (~35 ms). The PWN contribution should lead to a distinct spectral feature which can be probed by future instruments such as CTA.