I have three questions for this post: What might have put Mormons and horns in the same sentence? How might the verbs in those sentences have changed to “have” or “grow”; and Is there evidence that the verbs actually did so change?
Horned by Association
Mormons are like X => X have horns => Mormons have horns. Candidates include Native American Peoples,  White vigilantes (see image),  “Orientals,”  religious revelers,  members of secret societies,  practitioners of black arts,  Jews,  Catholics, and demons. Each (allegedly) had/wore horns and were used to describe Mormons. It’s a big jump, however, from one group wearing horns to a second group growing them—especially when the first group doesn’t.  Mormon horns are more likely cousins than children of their Jewish, Catholic, and Masonic counterparts. Parsimony chooses “Mormons => evil => horns” over “Mormons => Jews => evil => horns.”
Horned by Literalization
Mormons are monsters => Monsters have horns => Mormons have horns. Mormon “fiends,” “demons,” “monsters,” “brutes,” and the like might be interpreted in a literal sense by non-fluent speakers, credulous individuals, and children. 
Horned by Muddling
Since folk myths need not be logical, we can entertain “big jump” conjectures. For example, many observers classified Mormons as polytheists and many polytheistic belief systems include horned gods.  Mormon are polytheists => polytheists worshipped gods with horns => Mormons have horns. Like I said: big jump.
Horned by Sexual Deviance
The supposed animal sexuality of Mormons could inspire a horned caricature following the path established by fertility gods, revelers, and farm animals—and possibly literalized belief.
Karl Young conjectured in 1971 that “cynical non-Mormons” would expect polygamous wives to stray, thus “bestowing upon him [her husband] a pair of horns”—a traditional idiom for cuckoldry.  Young provided no evidence for the hypothesis, and I haven’t found any to fill the gap. Further, descriptions of Mormon horns follow, word for word, descriptions of contemporaneous Catholic and Jewish horns; polygamy can’t explain Mormon horns but have nothing to do with the others. (More on this in a subsequent post.)
Horned by Biology or Magic
In the present connection, the Elder missionary haircut boggles the mind. Where do you hide horns?  Of course, if folk myths were logical, we’d just call them “logic.” In the nineteenth century, understandings of biology and/or the supernatural among at least some portions of the populace reduced the necessary imaginative leaps. Most commentators believed moral character manifested in the body and could transfer to descendants.  Hypothetically, someone could have identified horns as a consequence of the Mormon lifestyle. Alternately, exposure to witchcraft or other Dark Arts might bestow horns and the ability to conceal them supernaturally.  Mormons might have been imagined to unmask in the temple.
Evidence Isn’t Near As Much Fun and Is Lots Harder to Find
I found no documents that I could, with a straight face, construe as evidence for any of the above hypotheses. The only connections I found supported were to the beasts in Revelations and to the medieval image of Satan—and these almost all clearly intended figuratively.
For emphasis: hypothesizing was fun and finding documents conjoining Mormons and the various hypotheses are not difficult (ht: GoogleBooks), but I don’t see any evidence to bear the above ideas out.
Mormon Horns 1, 2, 3, 4, 5, 6, 7. These horn posts continue earlier efforts analyzing ways of describing Mormons or using Mormons to describe something else. These include: India, Cows, Bluebeard, Lice, Crickets, Flies, Happy Valley, and sundry other beasts.
 Indians: Mormons and Native American Peoples entered the public imagination together in several ways. Mormons proselyted among Indians and some Indians joined the church; various Indian groups at different times warred against and treated with Mormons separately from their relations with non-Mormon Whites and US federal government agents; Mormon teachings and the Mormons’ respective geographic situations placed special emphasis (from the Mormon and various Native American perspectives) on the relations with and status of Native American Peoples; some Mormons dressed as Indians at the Mountain Meadows Massacre and may or may not have done so at other times; some observers implicated Mormonism in the Ghost Dance movement; some observers alleged that Mormons were becoming like Indians; and so on.
Examples of Native American Peoples using horned headdresses, see Figure: Sia Buffalo Mask, photographed by Edward Curtis, 1926, Library of Congress #USZ62-47017; “Their headdresses consisted of a band, wound with different colored calico, fitting over the head like a crown. There were attached to this band, one over each ear, two representations of horns made of slats of wood curved and painted.” J Walter Fewkes, “Hopi Basket Dances,” The Journal of American Folklore 12:45 (1899 Apr-Jun): 88 [81-96].
Examples of Mormons dressing as Indians or being accused of such: “I am in possession of the evidence that bands of these Salt Lake Mormons, armed, dressed, and painted—having the appearance of Indians—are stationed on the way to California and Oregon, for the purpose of robbing the emigrants. Many murders and robberies have already been committed by these demons in human shape, which have been published to the world and attributed to the Indians.” William Smith in Melchizedek and Aaronic Herald 1:8 (1849 Feb), as quoted in Ellen E. Dickinson, New Light on Mormonism (New York: Funk & Wagnalls, 1885), 138-9; “When they reached the locality where the bloody tragedy I am about relating [the Mountain Meadows Massacre] was enacted, their stock was first run off by what appeared to be Indians, but really Mormons disguised as such.” William Elkanah Waters, Life among the Mormons, and a March to Their Zion: To Which Is Added a Chapter on the Indians of the Plains and Mountains of the West (New York: Moorhead, Simpson & Bond, 1868), 188-9. Ronald W Walker, Richard E Turley Jr, and Glen M Leonard, Massacre at Mountain Meadows (New York: Oxford University Press, 2008); Will Bagley, Blood of the Prophets: Brigham Young and the Massacre at Mountain Meadows (Norman, OK: University of Oklahoma Press, 2003).
Examples of Mormon involvement in Native American ceremonial life: “[I]t is sufficiently evident that the Mormons took an active interest in the religious ferment then existing among the neighboring tribes and helped to give shape to the doctrine which crystallized some years later in the Ghost dance.” James Mooney, The Ghost-Dance Religion and the Sioux Outbreak of 1890, part 2 of the 14th Annual Report of the Bureau of Ethnology to the Secretary of the Smithsonian Institution, 1892-3, with JW Powell, director (Washington DC: Government Printing Office, 1896), 703-4. Gregory E. Smoak, Ghost Dances and Identity: Prophetic Religion and American Indian Ethnogenesis in the Nineteenth Century (Berkeley and Los Angeles: University of California Press, 2006), 71-80.
Secondary sources: For the varied representational relationship among Mormons and Native American Peoples, see W Paul Reeve’s current work, for example, “Red, White, and Mormon: Race and the Making of a Mormon-Indian Body,” paper presented at the Mormon History Association Conference, Springfield, IL, 2009 May 21-24. See also TL Givens, Viper on the Hearth, 55-7; Armand L Mauss, All Abraham’s Children: Changing Mormon Conceptions of Race and Lineage (Urbana, IL: University of Illinois Press, 2003); Charles S. Peterson, “Jacob Hamblin, Apostle to the Lamanites, and the Indian Mission,” Journal of Mormon History 2 (1975): 21-34; W Paul Reeve, Making Space on the Western Frontier: Mormons, Miners, and Southern Paiutes (Urbana, IL: University of Illinois Press, 2007).
 Vigilantism: Some anti-Reconstruction terrorist and/or vigilante groups in the American South used horns as part of their costume. [A] Mormon “Danites” were imagined to play similar roles of intimidation and retribution. [B] Mormons are insurgent => insurgent Southern separatists wear horns => Mormons have horns. The 1917 film A Mormon Maid portrayed Mormon Danites as wearing costumes very similar to those of the KKK. (See still showing horned costumes here; scroll down.) See also “The Bradys among the Mormons; or, Secret Work in Salt Lake City,” Secret Service: Old and Young King Brady, Detectives 239 (1903 Aug 21) [cover shown in post]. Givens (Viper on the Hearth, 120) identifies the issue as 964 (1917 Jul 13).
[A] For example: Testimony Taken by the Joint Select Committee to Inquire Into the Condition of Affairs in the Late Insurrectionary States: Alabama, Volume II, vol 9 of Report of the Joint Select Committee to Inquire Into the Condition of Affairs in the Late Insurrectionary States, Made to the Two Houses of Congress February 19, 1872, 13 vols (Washington DC: Government Printing Office, 1872), 680, 730, 813. [B] Rebecca Foster Cornwall and Leonard J. Arrington, “Perpetuation of a Myth: Mormon Danites in Five Western Novels, 1840-90,” Brigham Young University Studies 23 (Spring 1983): 147-65; Leonard J. Arrington and Jon Haupt, “Intolerable Zion: The Image of Mormonism in Nineteenth Century American Literature,” The Western Humanities Review 22 (Summer 1968): 243-60.
 Orientalism: In the nineteenth-century, White, Anglo-American popular imagination, Mormons and “Orientals” were very similar. [A] Some Asians and North-Africans, particularly the Druze, wore a decorative horn or a conical hat (see Figure). [B] Mormons are oriental => Orientals wear horns => Mormons have horns.
Mormons and Druze were compared explicitly: [Describing a letter written by a Druze addressed to fellow believers]: “Letter of Moktana, denouncing the blasphemies of Mohala, who taught promiscuous intercourse, such as was practised amongst the Nosairi. Moktana repeatedly reproaches the Christians with falling off to Judaism and Mahomedanism. He addresses them as an assembly of saints. There are many coincidences with the Mormons”; “They [Druzes] keep their religious worship a profound secret, and no one is allowed to enter their temples or see their religious books. They have an esoteric and an exoteric system of religion, the former designed for the common people, and the latter for the Akal or the initiated. They regard it lawful to dissemble their faith. They practice neither circumcision, praying, nor fasting. Polygamy and incess [sic] prevail among them. They are the Mormons of Syria.” [C]
[A] See, for example, Timothy Marr, The Cultural Roots of American Islamicism (Cambridge and New York: Cambridge University Press, 2006). [B] Jehan S Rajab, “The Tantour or Shihabbiyeen: The Tall Silver Head-dress of the Druze of Lebanon and Others,” website of Tareq Rajab Museum, Kuwait, accessed 2009 Aug 19; [C] David Urquhart, The Lebanon (Mount Souria): A History and a Diary, 2 vols (Thomas Cautley Newby, 1860), 1.45; No author listed, “Miscellaneous: The Druzes,” The American and Foreign Christian Union 11:9 (1860 Sep): 289 [289-90]. Photograph by Bonfils, (what would become) Lebanon, about 1870; Wikipedia.
 Bacchanalia/Saturnalia/Parties: One of the beliefs floating around was that after Mormons sat through sermons lasting six hours and longer, they cut loose into unhinged religious bacchanalias. Some wild religious parties, such as the Bacchanalia of ancient Greece, the Carnival of contemporary Rome, and the Charlton or Horn Fair near antique and contemporary London, involved people wearing horns. [A] Thus: Mormons are bacchanals => bacchanals wear horns => Mormons have horns.
Mormons explicitly associated with ancient bacchanalias: “Some ran franticly through the woods day and night, uttering unintelligible sounds; some went into convulsions and lost their reason through overpowering religious emotion; while the country around seemed as the plains of Boetia must have seemed during the high festivals of Bacchus”; “I presume Nauvoo is as perfect a sink of debauchery and every species of abomination, as ever were Sodom or Nineveh”; “…a member of Congress…said that a gentleman…told him…that doings akin to a Saturnalia were quite a common thing among the people—the promiscuous mixing of the sexes indulging in unrestrained license.” [B]
Mormons, as in many other instances, returned the favor of associating anti-Mormons with or identifying them as worse than revelers. For example: [Criticizing government anti-polygamy action]: “And where was this scene enacted? … Was it at the destruction of the cities of Sodom and Gomorrah… or in Pompeii or Herculaneum, who, in their turn, for their libidinous and unrighteous practices… suffered the vengeance of eternal fire? No. Was it in the Saturnalia of the Bacchanals of ancient Greece and Rome? No. … Was it during the reign of the first French republic…? No. Was it in the days of the inquisition…? No. Was it under the influence of Bacchus, or in the midnight reveling as exhibited in Rome under Nero? No. This scene was enacted in mid-day, in the 19th century, in the year of our Lord, 1884, in the Federal Court House in Salt Lake City….” [C]
[A] John Lempriere, A Classical Dictionary; Containing a Copious Account of All Proper Names Mentioned in Ancient Authors, with the Value of Coins, Weights, and Measures Used Among the Greeks and Romans, and a Chronological Table, 3rd ed (Philadelphia: James Crissy, 1822), “Mimallones”; Bela Bates Edwards, “The Roman Catholic Religion in Italy,” speech first delivered 1848 Jul, in Writings of Professor B. B. Edwards, with a Memoir by Edwards A Park, 2 vols (Andover, MA: WF Draper, 1858), 2.29; William Pulleyn, “Horn Fair,” The Etymological Compendium, or, Portfolio of Origins and Inventions, 2nd ed (London: Thomas Tegg, 1830), 167-168. [B] No author listed, “The Yankee Mahomet,” The Independent 50.2598 (New York: 1851 Jun): 561 [554-564]; A Missionary in Western Illinois, “Crisis of Mormonism Approaching,” The Home Missionary 15:4 (1842 Aug): 78; John Taylor, [citing a “Bro. Cannon” (presumably George Q Cannon), citing an unidentified Congressman], speech in Salt Lake City, 1882 Feb 12, JD 24.96-7. [C] John Taylor, speech at Ogden, UT, 1884 Oct 19, reported by John Irvine, JD 24:358 [341-359].
 For example, an 1874 text on Freemasonry connected the Classical figure Pan with the Christian Satan, “so that to the common mind the Devil was represented by a he-goat, and his best known marks were the horns, the beard, and the cloven hoofs. Then came the witch stories of the Middle Ages, and the belief in the witch orgies, where, it was said, the Devil appeared riding on a goat. These orgies of the witches, where, amid fearfully blasphemous ceremonies, they practised initiation into their Satanic rites, became, to the vulgar and the illiterate, the type of the Masonic mysteries; for, as Dr. Oliver says, it was in England a common belief that the Freemasons were accustomed in their Lodges ‘to raise the Devil.’” Albert Gallatin Mackey, An Encyclopædia of Freemasonry and Its Kindred Sciences: Comprising the Whole Range of Arts, Sciences and Literature as Connected with the Institution (Philadelphia: Moss, 1874), “Goat, riding the,” 315.
For an example of a Mormon instantiation, JH Beadle’s 1870 Life in Utah provided an engraving showing alleged portions of the endowment, including a group of naked initiate women; sacrificial altar with human on it and an officiant with a knife at the “sacrifice’s” throat (and a caption about a “trial of faith”); an officiant with tall, horn-like Catholic-bishop-like hat; an actor portraying Satan with a pointy hat; and murdered apostates. JH Beadle, Life In Utah; or, The Mysteries and Crimes of Mormonism. Being an Exposé of the Secret Rites and Ceremonies of the Latter-Day Saints, with a Full and Authentic History of Polygamy and the Mormon Sect from Its Origin to the Present Time (Philadelphia: National Publishing Company, 1870), 486.
Perhaps you’ve heard, “don’t fall off the goat…” in connection with Mormon liturgy?
 I haven’t chased down refs even though (let’s say, “because”) they are not hard to find: many people accused Mormons of practicing some sort of Satanism/occultism.
 On the origins of Jewish horns, see, for example, Raphael Patai and Jennifer Patai, The Myth of the Jewish Race, revised ed, Jewish Folklore and Anthropology Series (Detroit: Wayne State University Press, 1989), 13.
 Some of the connections depend on esoteric knowledge or tenuous associations and the KKK (and similar groups) came too late to inspire a connection made in the 1830s. The 1917 film A Mormon Maid , cited above, posits that the KKK took the idea from the Mormons and not vice versa. (There might also be an anti-German connection, with the round helmet and vertical center-spike, similar to the WWI German combat helmet).
 Literalization effects could derive from both speakers and hearers. As noted, some hearers, due to age, temperament, language skills, experience, etc., might miss layers of meaning. Some speakers might also, with an audience of such hearers, embellish reality for entertainment purposes. If, at Judgment Day, I am called to account for the strict accuracy of everything I’ve ever told my nephews… I’ll find out for myself if Satan has horns.
 Polytheism: For examples: the Celtic Cernunnos, the Hindu Pashupati, the Sumerian Anu (wore a crown with horns), and the Egyptian Ka-Amentt (sometimes a bull). I have not verified that people in the nineteenth century would have known about these particular deities.
Alternately, accounts of the temple ceremonies have circulated from early in Mormon history. There is a slight possibility that observers mixed up the portrayal of Satan by an actor with the worshipers.
 Karl E Young, “Why Mormons Were Said to Wear Horns,” in Lore of Faith and Folly, ed by Thomas E. Cheney (Salt Lake City: University of Utah Press, 1971), 111-112. Young provides no documentation connecting cuckold horns and Mormon horns. He merely establishes that cuckolds were said to wear horns, notes that in his youth the word “horny” described promiscuous young women, and concludes that Mormon horns must come from the same source.
Alternately—and not mentioned by Young—the few actual instances of Mormon polyandry, the allegations of much more polyandry, and the sealing of women to a church leader and not to the husband she lived with in mortality, plebian Mormon males could be said to be cuckolded by lecherous leaders. At any rate, the usage seems more entrenched in European culture than American, witness, for example, the Charlton or Horn Fair near London. If the cuckold conjecture is true, it seems likely that it would have arisen in England, with its large, mid-century Mormon population.
A horned cuckquean—a betrayed wife—would fit the Mormon situation more closely, but such usage occurred less frequently. The ignorance of the spouse is a key element of cuckoldry; the more precise term for an acquiescent husband in an openly polyandrous but legally monogamous marriage is “wittol.” I am not aware of a complementary term for an acquiescent wife; “Wittee” refers to the polyandrous wife of the wittol.
 There is also the issue of how an adult convert acquires horns—and what happens in the case of apostasy.
 Mormons’ supposed violence and confirmed polygamy founded reports and predictions of altered physiognomy and physiology. The trend is well established in the literature. For example: “The Turks, when they wrested from the effete Bysantine Greeks their Territories…, were fresh and vigorous with the enduring strength derived from the spare diet afforded by the desert waters of Turkistan, and were able to procreate the janizary which for generations was the invincible and conquering foe of Christendom. But with the introduction of the harem, …they were soon obliged to have recourse to premiums offered for the enlistment of foreign physiques…. Even during the comparatively short duration of Mormon lechery in the United States, the same effect was clearly apparent in depreciated physical and mental power.…” NO Eilims, “Marriage Compatibility,” Letter to the editor of Medical Brief 10:7 (St. Louis: 1882 Jul): 317-8; Lester E Bush Jr, “A Peculiar People: The Physiological Aspects of Mormonism 1850-1975,” Dialogue: A Journal of Mormon Thought 12:3 (Fall 1979): 61-83; Gary L Bunker and Davis Bitton, “Polygamous Eyes: A Note on Mormon Physiognomy,” Dialogue: A Journal of Mormon Thought 12:3 (Fall 1979): 114-119.
 For overview and analysis, see Michael D Quinn, Early Mormonism and the Magic World View (Salt Lake City: Signature, 1984); Richard Lyman Bushman, Joseph Smith: Rough Stone Rolling (New York: Knopf, 2005). For easily multiplied example, one story related that Smith used “his magic white stone” and a “hazel wand” to find buried treasure, but someone spoke while digging it up, which broke the spell and moved the treasure out of reach; Smith explained the problem and prescribed the sacrifice of a black sheep to guarantee success. According to the relaters, Smith avoided delivering any treasure on a contrivance and, in the process, gained the meat of the sheep for his table. Pomeroy Tucker, “The Mormon Imposture — The Mormon Aborigines,” Wayne Democratic Press 3:3, Lyons, NY: 1858 Jun 02, transcribed by Dale Broadhurst, <http://sidneyrigdon. com/dbroadhu/NY/miscNYS3.htm>, 2009 Sep 02. Another newspaper account: AW Cowles, “The Mormons: Pen and Pencil Sketches Illustrating Their Early History, I,” Moore’s Rural New Yorker 20:1 (Rochester, NY: 1869 Jan 02), transcribed by Dale Broadhurst, accessed 2009 Sep 02; image illustrating the anecdote: AW Cowles, drawing, “Sacrifice of a Black Sheep” in “The Mormons: Pen and Pencil Sketches Illustrating Their Early History, III,” Moore’s Rural New Yorker 20:4 (Rochester, NY: 1869 Mar 20), accessed 2009 Sep 02.