To assign video categories to menus you can try the following:
1. Go to Appearance -> Menus in WordPress administration;
2. In Screen Options tab (top right of the page) make sure you have chacked Video categories;
3. Choose the categories you want to put into the menu and save the menu.
This should do it, please let me know how it goes.