Unfortunately there are no instructions because navigation is very different for each and every theme and installation. Navigation menus does not support shortcodes by default unfortunately.
Most themes have the navigation code located in the header.php file, but you might have to ask the theme author about that. After locating the correct file and the navigation code, the PHP search shortcode is needed to be inserted into the correct location. To where exactly, it's impossible to tell, it depends on the menu structure, code and style.
If you want I can take a look at the theme code for you, and if you have a desired location, I might be able to quickly put the shortcode there (I can't promise this though, but I can try). In this case I'm going to need temporary back-end and FTP access to do so. Please make sure to back-up all the files and database to make sure nothing gets lost 🙂Best,
If you like my products, don't forget to rate them on codecanyon :)