I've not deleted any previous Navigation destinations nor could I find a process to do so.
To delete bookmarks and history open the browser, tap menu, tap bookmarks, long press (press and hold) the bookmark you want to delete, a new window will oped, tap delete bookmark. History is similar. Open bookmarks, tap history, tap the bokmark, long press, tap delete.