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.