The fact is you can only keep 5 horses registered and I wasted some of those slots with random horses. I've browsed through all the menus but can't find the option to set free a horse so I can get another one. Does any one know how can I achieve this or any way to register more than five horses? I have the official guide of the game and can not find any information about this topic.
As said by Seiyria, you can kill a horse but that is a bit creepy.
So otherwise, there's a guy on the way to Gerudo who asks you to sell him a horse for 300, so it might be better to give your horse to him rather than killing him ;)
And I haven't tried this yet, but it seems that if you talk to the guy at the stable about registering a new horse when you already have 5, he will ask you if you want to free one.
One possible way to set a horse free is to take it to Hyrule Castle and feed it to a Guardian.
Well you can take your new horse up to the stable and say you want to register your horse. It will say that you have too many horse and it’ll say you need to set one free! Your welcome!