It is a prepositional phrase functioning as an adverb: (See also ironmikezero's link.)

But, at the same time, if you mean it either figuratively, as in "stood motionless", or more literally, as in "turned into stone" or some force petrified him, while it certainly looks like a prepositional phrase, it may not be entirely appropriate to break those two words out from what is a three word idiomatic phrase since the literal meaning of "turned to stone" (without an object) would be something like he turned to face a/the stone. If you add an object, as in he turned to stone him/her, then it become an infinitive.