You could use ReReplacer Pro to find and remove the menu item from your HTML output based on a custom PHP condition.
You just need to figure out the line(s) of PHP code to get the cookie and check for it (pretty basic).
The free version doesn't have the conditions. So you can only test if you can make the menu item be removed on all pages.
There is a 30-day money-back guarantee. So you can buy it, set it up. And if you are not happy with it, ask for a refund.