New Radio (NR) supports operations at high frequency bands (e.g., millimeter wave frequencies) by using narrow beam based directional transmissions in order to compensate high propagation losses at such frequencies. Due to the limited spatial coverage with each beam, the broadcast transmission of paging in NR is performed using beam sweeping, which takes multiple time slots. Thus, paging procedure used in NR would substantially increase downlink resource overhead of the network with directional transmissions. Such overhead would further increase as we move higher in the frequency bands, such as terahertz bands, which is being viewed as one of the potential enabling technologies for future generation networks. Therefore, the NR based paging solution is incapable of supporting highly directional systems. In this paper, we propose a novel minimal feedback enabled paging mechanism which, instead of using all the beams for paging transmissions, only activates sub-set of beams having one or more UEs under the coverage. UE presence indications are implemented to identify the correct set of beams to be activated. Our analytical analysis and simulations show that the proposed solution significantly reduces the downlink paging overhead compared to the NR based solution (e.g., more than 80% gain for a system with 256 number of beams) while incurring minimal energy cost at the UE side.