Hi!
WordPress does not allow putting shortcodes to menus unfortunately. The only possible way is to edit the corresponding PHP file and put the search shortcode before or after the menu element.
Ususally the header menu is displayed in the header.php file in your active theme directory. You will have to use the PHP shortcode of the plugin: https://goo.gl/DLrp2n