When option Video post type is public is enabled (plugin Settings, tab Post options), the plugin custom post type, category taxonomy and tag taxonomy can be added into custom menus under Appearance – Menus.

If they are not present into the menu assignment sidebar, simply open Screen Options when editing a menu and check any of the following (depending what you want to add to the menu): Vimeo Videos (for video custom post type), Vimeo Video categories (for video categories) or Vimeo Video tags (for video tags).
Once checked you will be able to find them into the menu assignment sidebar.

WordPress plugin Vimeo Video Post - custom menu

More details on how to create custom menus can be found in WordPress Codex.