Replacing words with synonyms is probably the first thing to try, but be careful not to miss multiple words expressions and idioms. Also, make sure you choose a synonym with the same part of speech.
they look for a good solution < ! > they view/stare/... for a good solution
they work hard < ! > they job/task/… hard
More complicated rephrasing is only possible if you use some level of grammatical analysis. You should at least recognize constituents within a sentence.
Here are some examples for rephrasing which take into consideration the grammatical structure of the sentence:
the dog ate my homework < > my homework was eaten by the dog (passivisation)
the bone of the dog was stolen < > the dog’s bone was stolen (possessive rephrasing)
she sent him a letter < > she sent a letter to him (verb complements replacing)
my name is Bond < > Bond is my name (copular)
the cat ate the cake < > it was the cat who ate the cake (cleft)
Have a look at Contextors API and its Voice Conjugator