It's in the panel menu of the Hyperlinks panel. It's in the panel menu of the Cross-references panel.
It's missing from the contextual menu (someone forgot it?)
You can add a keyboard shortcut: Edit > Keyboard Shortcuts > Product Area: Panel Menus > Hyperlinks: New Hyperlink Destination.
Thank you for your response. You've helped me make some progress (see below), though YES... it's missing! Originally I was in "Essentials," (what CC 2015.4 apparently defaulted to) but I changed to "Interactive for PDF" and the Hyperlinks panel appeared!? Never the less, the options is still missing from the Hyperlinks contextual menu.
If you have further comments, I'd appreciate hearing them. In the meantime, I can get some work done. Thanks!
I marked Steve's answer as "Assumed Answer" because I'm assuming Adobe decided to get rid of the "New Hyperlink Destination" option in the Interactive menu.
I changed it to Answered. "Assumed Answered" is a useless feature of the forum software that means nothing.