The stone, which apparently resembles a small man with a sack over his back, is said to have once been a man, petrified when he tried to steal books from the church at Llandyfrydog*. The rock runs around its field three times on Christmas Eve when it hears the church bell strike twelve (midnight presumably). Tales of petrified wrong-doers are common stock around stones: Grinsell* lists 19 others in Britain, of which at least 9 were also for standing in the way of christianity or breaking the Sabbath tabu in some way. He suggest that such legends date from the 17th century, when the idea of a divine judgement for Sabbath-breaking was a popular theme in church sermons.
This suggests the folklore about the theft is more recent, which might explain why the church isn't mentioned in the wonder (if we accept they are the same site). The current church is 14th-15th century (*p.174), however, the church is named after St. Tyvrydog, and may therefore have been founded as early as the 5th century1. Despite this, if the tale of the theft was of any age at all, it would be more likely to mention the saint petrifying the thief, matching other thief-petrifications by early saints, like Illtud who turned two thieves into stone2. That said, this may have been the original story and this element lost over time. Either way, moving stones stand on their own as a folklore element, with Grinsell* listing some 38 other rocks/sets of rocks which are said to move.
The good people at the Modern Antiquarian list a lot of Grinsell's sources for this rock in more detail, and include some other folkore about this area: you can find this (and some photos) on their Carreg Leidr page.