Joomla permissions don't work in reverse so you can't remove something by giving the user more permissions (e.g. going from Public to Registered). Only way to do this is with a dynamic menu, a menu module that has a specific spot for login/logout links, or template with specific module position. You could also use CB Content module and construct a menu with HTML as this will allow you to use substitutions so you could have dynamic links based off various profile credentials. It maybe possible on J1.7 with a new accesslevel that includes Public yet not Registered, but I haven't tried that.