If clicking the stars inside Google Maps fails to remove them (try double clicking. A window with a star-"save" shows up clicking on the star toggles on/off), visit Google Bookmarks. Starred items from Google Maps are also stored here and you should see a [remove] link to remove the bookmark. This will remove the starred item from Google Maps, but perhaps not immediately. You may need to close your browser or just wait for the update to take place. Visiting an international version of Google Maps might force the update if you have removed the item from your bookmarks but it is still displaying in the starred items section of Google Maps. For example, if you usually use maps.google.com, try visiting maps.google.com.au instead.