The idea of executing heretics by burning, actually began in the East in the time after the rise of Islam in 700, where heretics influenced by Zoroastrian dualism began to infest the Church, provoking wars and allying with the Muslim powers.
The death sentence was introduced because of the danger to society and the Empire these people caused. Because the Zoroastrians worshipped fire, this was thought to be a fitting way to execute them.
Here is a first person account of the end of a bogomil leader around 1000 AD from the Princess Anna Comnena. It gives some idea of the unsympathetic attitude prevalent with regard to this type of sentence.
fordham.edu/halsall/basis/AnnaComnena-Alexiad15.html
X However all the members of the holy synod and the chief monks, as well as the patriarch of that time, Nicholas, decreed that Basil who was the heresiarch and quite unrepentant, deserved to be burnt. The Emperor was of the same opinion and after conversing with him several times and recognizing that the man was mischievous and would not abandon his heresy, he finally had an immense pyre built in the Hippodrome. A very large trench was dug and a quantity of wood, all tall trees piled up together, made the structure look like a mountain. When the pile was lighted, a great crowd slowly collected on the floor and steps of the circus in eager expectation of what was to happen. On the opposite side a cross was fixed and the impious man was given a choice, for if he dreaded the fire and changed his mind, and walked to the cross, then he should be delivered from burning. A number of heretics were there watching their leader Basil. He shewed himself contemptuous of all punishment and threats, and while he was still at a distance from the fire he began to laugh and talk marvels, saying that angels would snatch him from the middle of the fire, and he proceeded to chant these words of David’s, ‘It shall not come nigh thee; only with thine eyes shalt thou behold.’ But when the crowd stood aside and allowed him to have a free view of that terrifying sight, the burning pyre (for even at a good distance he could feel the fire, and saw the flames rising high and as it were thundering and shooting out sparks of fire which rose to the top of the stone obelisk which stands in the centre of the Hippodrome), then the bold fellow seemed to flinch from the fire and be disturbed. For as if wholly desperate, he constantly turned away his eyes and clapped his hands and beat his thigh. And yet in spite of being thus affected by the mere sight he was adamant. For the fire did not soften his iron will, nor did the messages sent by the Emperor subdue him. … Then they ‘recognizing the web from the edge,’ took him and pushed him, clothes, shoes and all, into the middle of the pyre. And the flames, as if deeply enraged against him, ate the impious man up, without any odour arising or even a fresh appearance of smoke, only one thin smoky line could be seen in the midst of the flames. For even the elements are excited against the impious; whereas, to speak truthfully, they spare those beloved of God, just as once upon a time in Babylon the fire retreated from those young men who were dear to God, and enclosed them like a golden chamber. In this case the men who lifted up the accursed Basil had scarcely placed him on the pyre before the flames seemed to dart forward to snatch hold of him. Then the people looking on clamoured loudly and demanded that all the rest who belonged to Basil’s pernicious sect should be thrown into the fire as well, but the Emperor did not allow it but ordered them to be confined in the porches and verandahs of the largest palace. After this the concourse was dismissed. Later, the godless ones were transferred to another very strong prison into which they were cast and after pining away for a long time died in their impiety.
i