Device-to-Device communications are expected to play an important role in current and future cellular generations, by increasing the spatial reuse of spectrum resources and enabling lower latency communication links. This paradigm has two fundamental building blocks: (i) proximity discovery and (ii) direct communication between proximate devices. While (ii) is treated extensively in the recent literature, (i) has received relatively little attention. In this paper we analyze a network-assisted underlay proximity discovery protocol, where a cellular device can take the role of: announcer (which announces its interest in establishing a D2D connection) or monitor (which listens for the transmissions from the announcers). Traditionally, the announcers transmit their messages over dedicated channel resources. In contrast, inspired by recent advances on receivers with multiuser decoding capabilities, we consider the case where the announcers underlay their messages in the downlink transmissions that are directed towards the monitoring devices. We propose a power control scheme applied to the downlink transmission, which copes with the underlay transmission via additional power expenditure, while guaranteeing both reliable downlink transmissions and underlay proximity discovery.