…down the primrose path
The association between primrose and pleasure comes from its status as an early spring flower, and that flower's association with maidens and pleasure. According to the Oxford English Dictionary, the word comes from Anglo-Norman primerose, lit. first rose. (Compare primerole, another word that referred to early spring flowers like the daisy, primrose, and cowslip.) The Middle English Dictionary entry gives lots of examples of early usage for primrose.
First, it helps to know that these flowers were eaten. Your question reminded me of a Middle English lyric, Maiden in the Mor, which uses the primerole as a food (mete) consumed by the eponymous maiden:
Welle was hire mete— wat was hire mete?
The primerole ant the, the primerole ant the—
Welle was hire mete— Wat was hire mete?
The primerole ant the violet.
What? Eat flowers? There is a naturalistic edge to this (surviving only on flower), but primrose was also known as a pleasurable, sweet food! In a late medieval cookbook (BL Harley 279), mixing up flowers to eat was delicious (again from the Middle English Dictionary):
a1450 Hrl.Cook.Bk.(1) (Hrl 279)25 : Prymerose: Take oþer half-pound of Flowre of Rys, iij pound of Almaundys, half an vnce of hony & Safroune, & take þe flowre of þe Prymerose, & grynd hem, and temper hem vppe with Mylke of þe Almaundys, [etc.].
(Primrose: take other a half-pound of flower of rice, 3 pounds of almonds, half an ounce of honey and saffron, and take the flower of the primrose, and grind them and temper them up with almond milk.)
So we have flowers, eating, and maidens. Any eroticism is through association with spring and maidens, who are (a) pure and (b) ready for sex, marriage, and/or childbirth. Here is a stanza from the fifteenth century poem Ave Regina Celorum by John Lydgate, where the primrose is used to describe Mary:
Hayle! holy maydyn, modyr and wyfe,
That brought Israell out of captyuyte,
As sterre of Iacob by a prerogatyfe
With the blessyd bawme of thy virginite,
The holyest roote that sprang out of Iesse,
Prymrose of plesaunce, callyd flos florum,
Thou were tryacle ageyne olde antiquite,
Aue regina celorum!
Mary is the primrose of pleasure, the flos florum (flower of flowers). If there is any erotic sense here, it is subsumed under God and Mary's role as the divine maiden, mother, and wife. Still, the connection to pleasure is there, and it appears in other texts. For example, back to the Middle English Dictionary, there is this example from a fifteenth century lyric:
c1450 Excellent soueraine (Dc 95)136 : Farewell prymerose, my plesaunce.
Plesaunce is a common collocation for primrose, perhaps because of the alliteration. So the primrose is a flower of pleasure, either in taste or in other figurative use.
In these and other examples, I find no reference to such pleasure being a negative thing. Given that absence (an an Early English Books Online search mainly revealed references to herbology or to people in positive senses) I suggest that any negativity would be context-dependent. So the notion of the primrose path as negative depends on its context in Shakespeare, not on any quality of the primrose.
TL;DR: Shakespeare was the first to coin those phrases (or, at least, his is the first recorded use of those phrases), but primrose itself does not have the negative connotations you assert (nor, primarily, do the phrases). The negative outcomes would be from blindly following a path of pleasure.
Starting with your second question, because it has the more definitive answer:
Was William Shakespeare the first to associate primroses with deceit and casual love affairs?
According to the OED, he is the first to coin those two phrases, although, as I argue below, he does not really "associate primroses with deceit and casual love affairs". Its earliest citation for primrose path is 1604 in Hamlet:
Doe not as some vngracious pastors doe,
Showe me the step and thorny way to heauen
Whiles a puft, and reckles libertine
Himselfe the primrose path of dalience treadsHamlet, Act I, Scene iii
and the earliest citation for the related primrose way is "about 1616" in Macbeth:
Some of all Professions, that goe the primrose way to th'euerlasting bonfire
Macbeth, Act II, Scene iii
Their next citations are both in the latter half of the 18C (1763 and 1781 respectively).
For the second question:
Why did the primrose have such a negative reputation? When did English first use the primrose as a symbol of debauchery and overindulgence?
the answer is less clear: my view is that primrose itself does not have those negative connotations – rather it would be "blindly following the primrose path" that could lead to negative consequences. In support of this view, the OED's entry for primrose path is:
primrose path, n.
a path abounding in primroses; (figurative) an appealing course or route; esp. the pursuit of pleasure which might bring ruin or disastrous consequences (usually with allusion to Shakespeare's Hamlet: see quot. 1604).
where I see the primary allusion is to "an appealing course" or "the pursuit of pleasure" and where the "might bring ruin or disastrous consequences" is almost secondary.
As to why a specifically primrose path: while Macbeth and Hamlet are the earliest citations of those phrases, the OED has earlier extended and figurative uses of the word primrose (dating from 1450 and 1590 respectively):
primrose, n
II. Extended and figurative uses.
3. figurative.a. The first or best; the finest or a fine example of something ; the ‘flower’, ‘pearl’, ‘pink of perfection’ (see pink n.5 3). Also as a term of endearment. Now rare (archaic and poetic in later use).
b. Prime; first bloom, first fruits (of). Obsolete.
So, a hedonist (seeker after pleasure) would be likely to follow a path to "the first or the best" or to someone in their "prime" or their "first bloom" (especially, one assumes, if applied to someone of the opposite sex). The "ruin or disastrous consequences" come from following that path to the exclusion of other concerns.