AFAIK you have to reset the TV to its factory settings and set it up again.
Some folk found this didn't clear the searches and the one time I was able to check it out, the saved searches were also on their PC. That is, it was at the google+youtube sites.
Be sure to check your google+youtube settings to see if you can disable search saving but sadly, those sites do keep such information.
Try this. Try duckduckgo.com next time.
I would like to know how to erase history on Google and YouTube in my Samsung Smart tv.