We present a comprehensive computational study of the phase diagram of the frustrated $S=1/2$ Heisenberg antiferromagnet on the honeycomb lattice, with second-nearest $({J}_{2})$ and third-neighbor $({J}_{3})$ couplings. Using a combination of exact diagonalizations (EDs) of the original spin model, of the Hamiltonian projected into the nearest-neighbor short-range valence-bond basis, and of an effective quantum dimer model, as well as a self-consistent cluster mean-field theory, we determine the boundaries of several magnetically ordered phases in the region ${J}_{2},{J}_{3}\ensuremath{\in}[0,1]$, and find a sizable magnetically disordered region in between. We characterize part of this magnetically disordered phase as a plaquette valence-bond crystal phase. At larger ${J}_{2}$, we locate a sizable region in which staggered valence-bond crystal correlations are found to be important, either due to genuine valence-bond crystal (VBC) ordering or as a consequence of magnetically ordered phases, which break lattice rotational symmetry. Furthermore, we find that a particular parameter-free Gutzwiller projected tight-binding wave function has remarkably accurate energies compared to finite-size extrapolated ED energies along the transition line from conventional N\'eel to plaquette VBC phases, a fact that points to possibly interesting critical behavior---such as a deconfined critical point---across this transition. We also comment on the relevance of this spin model to model the spin liquid region found in the half filled Hubbard model on the honeycomb lattice.