"Perseus Against the Monsters" (Italy;1963)?
This was a sword and sandal movie based on the legend of Perseus and Medusa. The Medusa looked like something from the mind of H.P. Lovecraft and was created by Carlo Rambaldi, the genius mechanical effects wizard who built E.T., the creature in "Alien" (1979) and other great monsters. I guess you could also say that the Medusa looks like a tree. You mentioned victims being turned to stone and Medusa turns men to stone. You also said the movie featured horses and this one does as well, since it takes place in ancient times. Here is a section of the 3rd user review from the IMDb.com page for this movie.
The second and the most remarkable thing about MEDUSA AGAINST THE SON
OF HERCULES is the Medusa itself. The Medusa in this film is a
tentacled monster instead of a woman with vipers for hair. When I saw
it for the first time my jaw was on the floor. It's by far the coolest
thing I've ever seen in a movie. A truly one of a kind creation. The
Medusa, totally in black, looks like an evil tree and moves around
with spidery roots and has a uber thick nest of tentacles for hair,
and it freezes men into statues of stone with its single huge glowing
white eye. We see it walk around in a misty landscape which is strewn
with marbled soldiers. Some might find it cheesy but I thought the
effect was amazing. The Medusa appears from head to toe, for several
seconds, in full frame. No CGI here. Very evocative. Like a 1960s
pulpy science fiction cover come to life. Carlo Rambaldi is a genius.
I wish the (uninspired) direction was at the level of Rambaldi's
imagination and it knew how to utilize the remarkable creation to the
Here is the entire movie from YouTube. It's under one of it's many alternate titles of "Medusa Against the Son of Hercules". You can see men finding Medusa's 'stoned' men and fighting the Medusa at 8:50 into the film. There is a lot of mist in the scene, which is common in 'peplums'. This may be why you thought the creature emitted smoke.