All of our WordPress plugins are GPL licensed, so as long as your theme is also GPL licensed and attributes our plugin according to the GPL, then you are more than welcome to incorporate it into your theme.
The Multi-level Navigation plugin is a very old plugin and you would be better off incorporating the PixoPoint Menu plugin IMO. It will eventually be replacing the Multi-level navigation plugin anyway.
IMO the best approach is to add support for our plugins by using the wp_page_menu() function in your theme. That way the plugin will immediately start working as long as someone uses the "auto theme support" option.