Why questions in linguistics are the hardest because we can only speculate. That being said, there is plenty of evidence to make an educated guess.
Lundquist 2016 defines rhotacism as “the replacement of a non [r] sound with [r].”
Inervocalic s (a letter, not a sound!) is found “only on the very earliest inscriptions” (Weiss 2009/2011),
e.g. IOVESAT, VALESIOSIO, ESED (all circa 500 BCE); NUMASIOI (700 BCE?).
We don't know for sure how intervocalic s was pronounced in Old Latin but there is good reason to believe it was a voiced fricative, [z], cf. Sihler 1995, who writes that rhotacism in Latin was “doubtless through the medium of [z].”
Thus, we reconstruct the change as
*s > *z > r
Not everyone agrees on whether it happened in Proto-Italic or just affected the Latino-Faliscan branch only. Weiss 2009/2011 argues it was "an areal feature that affected Latin, Faliscan, and Umbrian" (Umbrian belongs to the Sabellic branch).
On the other hand, ancient grammarians were aware of this change too - Varro is the most cited example. e.g.
In multis verbis in quo antiqui dicebant S, postea dicunt R (L.7.27).
As for dating, most evidence comes from texts. For example, Cicero talks about princeps L. Papirius Mugillanus "qui censor cum L. Sempronio Atratino fuit" and we learn about him that he "primum Papisius est vocari desitus."
Another example: in 312 BC "Idem Appius Claudius... R litteram invenit, ut pro Valesiis Valerii essent, et pro Fusiis Furii." Weiss 2010 interprets this passage the following way, "in redacting the senatorial roll in his capacity as censor in 312 BCE Claudius rewrote these nomina, formerly spelled with s, with the letter r."
Taking such evidence into consideration, we assume that rhotacism must have happened before the middle of the fourth century BC,
cf. Niederman 1906 “Or, si nous considérons que, de tous les mots d’une langue, ce sont les noms propres qui se transforment le plus lentement […], nous ne risquerons guère de nous tromper en affirmant que, dans les noms communs, le rhotacisme était un fait accompli des l’année 350 av. J.-C. environ” (p. 74).
Naturally, scholars have always wanted to explain rhotacism phonetically (why does it happen?). As Garrett and Johnson 2011 astutely observe that historical linguistics textbook classify sound changes rather superficially, arguing that “an explanatory classification of surface patterns should reflect a typology of causes” (i.e it should be articulatory or acoustically oriented). They explain rhotacism with the help of aerodynamic constraints (a bias against voiced fricatives); in other words, voiced fricatives tend to become glides.
Cf. Solé 1992, who argues that z > r is due to “hardware constraints which are built into the physical system used for speech” or Painter 2012, who concludes that “rhotacism is the result of the listener reanalyzing phonetic realizations of a target /z/ in the speech signal as belonging to /r/.”
Naturally, rhotacism didn't happen simultaneously in all contexts - that is why there are numerous exceptions - below is my summary of exceptions, based on Baldi 2002: 285-290; Leumann 1977 and Sihler 1995, §172-173.
Leveling, e.g. arbor;
Borrowings (they were borrowed either later or from non-rhotacizing donor languages), e.g. basis, casa, Musa, rosa etc.;
Words that originally had ss: causa, formosa, quaeso, visus, usus etc.;
Next syllable begins with r, e.g. Caesar, miser (but: soror, aurora) etc;
Derivationally transparent compounds: e.g. desino, nisi etc.
Why are there so many exceptions?
A pretty common view to rhotacism is to treat it a multi-stage, diachronic process (starting with Touratier 1975; also see Baldi 1994). The best description of rhotacism I'm aware of is Roberts 2012. His model has five stages, starting with stage 0 - he calls his a phonetic tendency - when "co-articulatory pressures cause intervocalic voiceless consonants to tend to be realised as voiced" and concluding with stage L, when rhotacism became "a systematic property of the lexicon, subject to extension by analogy" and when rhotacism was "no longer productive over new VsV sequences, such as in
loans or those created by the degemination of ss."
Sihler 1995 observes that rhotacism may seem “extreme” phonetically but it is attested in many languages: in West Germanic languages and in Old Norse (Ringer and Taylor 2014, pp. 82-88), in some Greek dialects (Elean, Euboean, Eretrian etc.; Lundquist 2016) or in some Spanish dialects (Solé 1992).
Baldi, Philip. 1994. Some Thoughts on Latin Rhotacism. General Linguistics 34: 209-216.
Baldi, Philip. 2002. The Foundations of Latin. Berlin: De Gruyter.
Garrett, Andrew, and Keith Johnson. 2011. Phonetic bias in sound change. UC Berkeley Phonology Lab Annual Report.
Lundquist, Jesse. 2016. "Rhotacism." Encyclopedia of Ancient Greek Language and Linguistics. Brill Online.
Leumann, Manu. 1977. Lateinische Laut- und Formenlehre. München: C.H. Bech.
Niedermann, Max. 1906. Précis de phonétique historique du latin. Paris: C. Klincksieck.
Painter, Robert Kenneth. 2012. Acoustic and perceptual explanations for rhotacism in Latin and Germanic. Doctoral dissertation.
Ringe, Donald A., and Ann Taylor. 2014. The development of Old English. Oxford: Oxford University Press.
Roberts, Philip J. 2012. Latin Rhotacism: A Case Study in the Life cycle of Phonological Processes. Transactions of the Philological Society, 110(1): 80–93.
Sihler, Andrew L. 1995. New comparative grammar of Greek and Latin. Oxford: Oxford University Press.
Solé, M.J. 1992. Experimental Phonology: the case of rhotacism. In W. U. Dressler, H.C. Luschützky, O. E. Pfeiffer & J. R. Rennison (eds.), Phonologica 1988, Cambridge: Cambridge University Press, pp. 259-271.
Touratier, C. 1975. Rhotacisme synchronique du latin classique et rhotacisme diachronique. Glotta 53.246-281.
Weiss, Michael L. 2009/2011. Outline of the historical and comparative grammar of Latin. Ann Arbor: Beech Stave Press.