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 treads
Hamlet, 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.
