"flat stone for paving," c. 1600, ultimately from Old Norse flaga "stone slab," from Proto-Germanic *flago- (from extended form of PIE root *plak- (1) "to be flat"). Earlier in English as "piece cut from turf or sod" (mid-15c.), from Old Norse flag "spot where a piece of turf has been cut out," from flaga.
Old English stan, used of common rocks, precious gems, concretions in the body, memorial stones, from Proto-Germanic *stainaz (source also of Old Norse steinn, Danish steen, Old Saxon sten, Old Frisian sten, Dutch steen, Old High German stein, German Stein, Gothic stains), from PIE *stoi-no-, suffixed form of root *stai- "stone," also "to thicken, stiffen" (source also of Sanskrit styayate "curdles, becomes hard;" Avestan stay- "heap;" Greek stear "fat, tallow," stia, stion "pebble;" Old Church Slavonic stena, Russian stiena "wall").
Sense of "testicle" is from late Old English. The British measure of weight (usually equal to 14 pounds) is from late 14c., originally a specific stone. Stone-fruit, one with a pit, is from 1520s. Stone's throw for "a short distance" is attested from 1580s. Stone Age is from 1864. To kill two birds with one stone is first attested 1650s. To leave no stone unturned is from 1540s.