When and where is calling menu_link_save safe and appropriate?
Yes, hook_enable() sounds correct.

To find examples, on way is look at what's using the function on drupalcontrib.org.  That points to menu_enable(), which is even a core function.