"I'm going to replace the words.
My shoes 'wasted' or 'used'. My shoes have been 'wasted' or 'used'.
My patience began to 'waste' or 'use'. My patience began to be 'wasted' or 'used'.
Maybe 'decay'/'destroy'/'rot' are better words."
Matthew's use of waste sounds closer to the mark. However, we would probably say: "My shoes
were a waste, because I seldom
wore them.".
"My patience began to wear thin" and "My patience began to wear out" are more like idioms, or fixed phrases in English. The concept is in the whole sentence, rather than in the individual words. Therefore, trying to replace, "wear thin" or "wear out", with similar words in a sentence to do with patience will never really work.
To me, "My shoes have been wasted" does not work, and actually sounds like American slang for killing.
(i.e. literally, "My shoes have been shot by someone". It may of course be fine in AmE, but I don't know that).
"Maybe 'decay'/'destroy'/'rot' are better words."
Unfortunately, not to me.
In BrE these words would more likely to be used with things like, fruit, trees, leaves, houses, chairs and other physical objects. You might say, "my shoes and socks rotted". But you would then probably need to explain why, because it would seem odd. Although, I suppose not so strange if you live in an area of high humidity.
"Wear out": means "they have been used so much they are starting to fall apart", it doesn't mean that they have
rotted, which is different and
usually implies water has been involved. "Wear",
here, carries the sense of "abrasion", which is usually caused by dry rubbing. This is why it works with shoes and "rot" does not. The soles of the shoes are wearing out because they have been rubbed so many times on the ground by walking in them.
I don't think we would ever use 'decay'/'destroy'/'rot' in relation to non-physical items, or concepts, like: "patience", "love", "harmony", or "emotion", unless you were being very poetic! For example; "My emotion has rotted, oh woe is me!" sounds, very, very, strange.
