A dispersive solid-phase microextraction (DSPME) sorbent consisting of poly(1,6-hexanediol diacrylate)-based polymer microspheres, with embedded graphene microparticles (poly(HDDA)/graphene), was synthesized by microfluidic emulsification/photopolymerization and characterized by optical microscopy and X-ray fluorescence spectrometry. This sorbent was applied for simple, fast, and sensitive vortex-assisted DSPME of rare earth elements (RREs) in coal fly ash (CFA) leachate, prior to their quantification by inductively coupled plasma mass spectrometry (ICP-MS). Among nine DSPME variables, the Plackett–Burman screening design (PBD), followed by the central composite optimization design (CCD) using the Derringer desirability function (D), identified the eluent type as the most influencing DSPME variable. The optimum conditions with maximum D (0.65) for the chelating agent di-(2-ethylhexyl) phosphoric acid (D2EHPA) amount, the sorbent amount, the eluting solvent, the extraction temperature, the centrifuge speed, the vortexing time, the elution time, the centrifugation time, and pH, were set to 60 μL, 30 mg, 2 M HNO3, 25 °C, 6000 rpm, 1 min, 1 min, 5 min, and 4.2, respectively. Analytical validation of the DSPME method for 16 REEs (Sc, Y, La, Ce, Pr, Nd, Sm, Eu, Gd, Tb, Dy, Ho, Er, Tm, Yb, Lu) in CFA leachate samples estimated the detection limits at the low ppt level, the recovery range 43–112%, and relative standard deviation within ± 22%. This method was applied to a water extraction procedure (EP) and acetic acid toxicity characteristic leaching procedure (TCLP) for leachate of CFA, from five different coal-fired thermoelectric power plants. The most abundant REEs in leachate (20 ÷ 1 solid-to-liquid ratio) are Ce, Y, and La, which were found in the range of 22–194 ng/L, 35–105 ng/L, 48–95 ng/L, and 9.6–51 μg/L, 7.3–22 μg/L, 2.4–17 μg/L, for EP and TCLP leachate, respectively. The least present REE in TCLP leachate was Lu (42–125 ng/L), which was not detected in EP leachate.