That's an interesting idea. I wish I could find more corroboration for this, but it looks like it can be used for negative (and possibly horrifying) effect:
Looking at Petrified condition description:
[...] If a petrified character cracks or breaks, but the broken pieces are joined with the body as he returns to flesh, he is unharmed. If the character's petrified body is incomplete when it returns to flesh, the body is likewise incomplete and there is some amount of permanent hit point loss and/or debilitation.
(All emphasis here and below are mine)
So, at the very least, you could maim or cripple someone with this procedure, e.g. deforming or removing his limbs, damaging his face to ruin his appearance or senses, or leaving gashes and holes in his flesh.
Moreover, note the difference in description of Stone to Flesh in PF versus 3.5E:
This spell restores a petrified creature to its normal state, restoring life and goods. The creature must make a DC 15 Fortitude save to survive the process. Any petrified creature, regardless of size, can be restored. The spell also can convert a mass of stone into a fleshy substance. Such flesh is inert and lacking a vital life force unless a life force or magical energy is available. For example, this spell would turn an animated stone statue into an animated flesh statue, but an ordinary statue would become a mass of inert flesh in the shape of the statue.
This spell restores a petrified creature to its normal state, restoring life and goods. The creature must make a DC 15 Fortitude save to survive the process. Any petrified creature, regardless of size, can be restored.
The spell also can convert a mass of stone into a fleshy substance. Such flesh is inert and lacking a vital life force unless a life force or magical energy is available. (For example, this spell would turn a stone golem into a flesh golem, but an ordinary statue would become a corpse.) You can affect an object that fits within a cylinder from 1 foot to 3 feet in diameter and up to 10 feet long or a cylinder of up to those dimensions in a larger mass of stone.
Maybe I'm reading too much into this, but note that between editions, an ordinary statue now becomes "a mass of inert flesh in the shape of the statue" rather than "a corpse". This suggests that any mass of stone added to the petrified character is something the spell 'doesn't know how to handle' - it won't create a complete and whole anatomy out of it (as in a corpse), but merely a mass of generic flesh.
So if you added stone wings to a petrified human, you won't end up with a winged human, but rather with a human with a pair of inert, fleshy growths generally shaped like wings - he won't be able to move them, and they'll just encumber him (and probably look quite grotesque, too).
I can't find much in the RAW to support this, and couldn't find anything to suggest you may gain a permanent benefit from this procedure. It obviously boils down to how your DM sees it.
However, it wouldn't make sense that this chain of effects will be a cheaper, stronger alternative to the effects of Permanency, which, for example, requires 2,500gp to permanently enlarge a target. Similarly, I couldn't find any permanent polymorph effect weaker than the 8th level spell Polymorph Any Object, so adding wings, limbs or other beneficial changes using the flesh-to-stone-to-flesh procedure seems really unbalanced.