When changing the type of modifier, you only need to stay sufficiently close to the original meaning of the sentence -- so if an adjective is most clearly expressed as an adverbial prepositional phrase, that's okay.
Still, an argument could be made that 'with his craftiness' could conceivably modify Odysseus. Consider "The man with a hat waved" and "The man waved with his hat." There, placement makes a difference as to how the phrase is understood. I'm not sure that's it's a good argument, mind you, but I can see the point.
'Fearless' has the same sort of problems. If the variations you've come up with adverbially convey substantially the same meaning, they're fine. And better, no doubt, than the convoluted 'Paul Revere, to whom fear was never attributed as a characteristic by those who knew him or wrote of him...'