I want to write something that means the same thing as "had changed destiny." I was going to use those words, but something didn't seem right. I googled that phrase, and came up with only one thing. So I don't think it's grammatically correct. Is it? What could I say that means the same thing?
There is nothing wrong with your had changed destiny grammatically. IF you don't like the sound of it, rephrase. You can use fate instead of destiny, altered instead of changed, you can change the grammatical structure of your sentence (use passive voice for example)
Someone's destiny was changed
Or there's another nice construction (don't remember it's proper grammatical name):
Someone had his/her destiny changed
There are tons of other ways to say the same thing
John's lies influenced Anne's fate.
John loved lying, artfully altering the very fate of those listening to him with only words.