"grilled with hot condiments," 1800; see devil. The notion is to make "hot" with mustard, pepper, etc.
Entries linking to devilled
Old English deofol "a devil, a subordinate evil spirit afflicting humans;" also, in Christian theology, "the Devil, a powerful spirit of evil otherwise known as Satan," from Late Latin diabolus (also the source of Italian diavolo, French diable, Spanish diablo; German Teufel is Old High German tiufal, from Latin via Gothic diabaulus).
The Late Latin word is from Ecclesiastical Greek diabolos, which in Jewish and Christian use was "the Devil, Satan," and which in general use meant "accuser, slanderer" (thus it was a scriptural loan-translation of Hebrew satan; see Satan). It is an agent noun from Greek diaballein "to slander, attack," literally "to throw across," from dia "across, through" (see dia-) + ballein "to throw" (from PIE root *gwele- "to throw, reach").
Jerome re-introduced Satan in Latin bibles, and English translators have used both words in different measures. In Vulgate, as in Greek, diabolus and dæmon (see demon) were distinct, but they have merged in English and other Germanic languages.
Meaning "false god, heathen god" is from c. 1200. Sense of "diabolical person, person resembling a devil or demon in character" is from late 12c. Playful use for "clever rogue" is from c. 1600. As an expletive and in expletive phrases from c. 1200.
Meaning "sand spout, dust storm" is from 1835 (dust devil is attested by 1867). In U.S. place names, the word often represents a native word such as Algonquian manito, more properly "spirit, god." Phrase a devil way (c. 1300) was originally "Hell-ward, to Hell," but by late 14c. it was a mere expression of irritation. Meaning "errand-boy in a printing office" is from 1680s, perhaps because they were often blackened by the ink (devils then being popularly supposed to be black).
Devil's books "playing cards" is from 1729, but the cited quote says they've been called that "time out of mind" (the four of clubs is the devil's bedposts); devil's coach-horse is from 1840, the large rove-beetle, which is defiant when disturbed. Devil's food cake (1895; three different recipes in the cookbook "compiled by the Ladies' Aid Society of the Friends' Church, Wilmington, Ohio"), rich and chocolate, probably is in deliberate contrast to angel food cake. Conventional phrase talk (or speak)of the Devil, and he's presently at your elbow is by 1660s.