What percentage of papers submitted to a conference or journal have been previously rejected in the same or another venue?
I haven't found anything in computer science, but this has been well-studied in other fields.

For example, one study1 surveyed authors from 923 scientific journals from the biological sciences in 2006-2008 and found that


  about 75% of published articles were submitted first to the journal that would publish them


(implying that 25% of published articles were rejected by another venue before finding their ultimate home).

A more common approach found in the literature is to follow up on the fate of rejected manuscripts from a particular journal (as opposed to the original target venue of published manuscripts).

For example, a study of manuscripts rejected by the British Journal of Surgery2 found:


  From the 926 manuscripts rejected by BJS, 609 (65.8 per cent) were published in 198 different journals with a mean(s.d.) time lapse of 13.8(6.5) months. Some 165 manuscripts (27.1 per cent) were published in general surgical journals, 250 (41.1 per cent) in subspecialty surgical journals and 194 (31.9 per cent) in non-surgical journals. The mean(s.d.) impact factor of the journals was 2.0(1.1). Only 14 manuscripts (2.3 per cent) were published in journals with a higher impact factor than that of BJS.


This trend is not especially new. Studies from decades ago also show large numbers of rejected papers being accepted somewhere, eventually. For example:

A study of 350 manuscripts rejected by the Annals of Internal Medicine, a general medical journal, during 1993 and 1994,3 found:


  Of 350 rejected manuscripts, 240 (69%, 95% confidence interval [CI]: 64% to 73%) were eventually published after a mean of 552 days (95% CI: 479 to 544 days, range 121 to 1,792 days). 


A study of papers submitted to the American Journal of Roentgenology in 19864 found: 


  At least 82% of the major papers and 70% of the case reports that are submitted to AJR are eventually published, either in AJR or elsewhere


An interesting study I came across measured the reverse phenomenon: published articles that are subsequently rejected5. 


  As test materials we selected 12 already published research articles by investigators from prestigious and highly productive American psychology departments, one article from each of 12 highly regarded and widely read American psychology journals with high rejection rates (80%) and nonblind refereeing practices.
  
  With fictitious names and institutions substituted for the original ones (e.g., Tri-Valley Center for Human Potential), the altered manuscripts were formally resubmitted to the journals that had originally refereed and published them 18 to 32 months earlier. Of the sample of 38 editors and reviewers, only three (8%) detected the resubmissions. This result allowed nine of the 12 articles to continue through the review process to receive an actual evaluation: eight of the nine were rejected.




1 Calcagno, V., E. Demoinet, K. Gollner, L. Guidi, D. Ruths, and C. De Mazancourt. "Flows of research manuscripts among scientific journals reveal hidden submission patterns." Science 338, no. 6110 (2012): 1065-1069. DOI: 10.1126/science.1227833

2 Wijnhoven, B. P. L., and C. H. C. Dejong. "Fate of manuscripts declined by the British Journal of Surgery." British Journal of Surgery 97, no. 3 (2010): 450-454. DOI: 10.1002/bjs.6880

3 Ray, Joel, Michael Berkwits, and Frank Davidoff. "The fate of manuscripts rejected by a general medical journal." The American journal of medicine 109, no. 2 (2000): 131-135. DOI: 10.1016/S0002-9343(00)00450-2

4 Chew, Felix S. "Fate of manuscripts rejected for publication in the AJR." AJR. American journal of roentgenology 156, no. 3 (1991): 627-632. DOI: 10.2214/ajr.156.3.1899764

5 Peters, Douglas P., and Stephen J. Ceci. "Peer-review practices of psychological journals: The fate of published articles, submitted again." Behavioral and Brain Sciences 5, no. 02 (1982): 187-195. DOI: 10.1017/S0140525X00011183