On distrowatch you can dig through the Linux distributions to make a list of which distro comes with what perl version. (I try to keep a CSV list up-to-date for System::Info).

A summary:

5.6    54 # .0: 16, .1: 38
5.8   372 # .0: 39, .1:  7, .2: 11, .3: 11, .4: 42, .5: 26, .6: 21, .7
+: 29, .8:184, .9:  2
5.10  270 # .0:105, .1:165
5.12  110 # .1: 10, .2: 24, .3: 36, .4: 40
5.14  166 # .0:  3, .1:  4, .2:156, .3:  1, .4:  2
5.16   59 # .0:  1, .1: 15, .2:  7, .3: 36
5.18  119 # .0:  8, .1: 31, .2: 77, .4:  3
5.20  145 # .0: 15, .1: 23, .2: 98, .3:  9
5.22  128 # .0: 12, .1: 74, .2: 36, .3:  6
5.24  137 # .0: 19, .1: 95, .2:  3, .3: 19, .4:  1
5.26  135 # .0: 19, .1: 72, .2: 41, .3:  3
5.28  117 # .0: 23, .1: 80, .2: 14
5.30   28 # .0: 28
[download]

If I limit that list to dists that got a release since 2017-01-01, I get:

5.8     2 # .8:  2
5.10   10 # .1: 10
5.12    4 # .3:  4
5.14    7 # .2:  6, .3:  1
5.16   15 # .3: 15
5.18   11 # .0:  2, .1:  1, .2:  8
5.20   44 # .0:  2, .2: 38, .3:  4
5.22   60 # .0:  1, .1: 44, .2:  9, .3:  6
5.24  121 # .0:  8, .1: 90, .2:  3, .3: 19, .4:  1
5.26  135 # .0: 19, .1: 72, .2: 41, .3:  3
5.28  117 # .0: 23, .1: 80, .2: 14
5.30   28 # .0: 28
[download]

and limiting to 2018 and 2019:

5.8     1 # .8:  1
5.10    4 # .1:  4
5.12    3 # .3:  3
5.14    5 # .2:  4, .3:  1
5.16   12 # .3: 12
5.18    4 # .0:  1, .2:  3
5.20   12 # .0:  1, .2: 10, .3:  1
5.22   30 # .1: 22, .2:  5, .3:  3
5.24   71 # .0:  2, .1: 54, .3: 14, .4:  1
5.26  108 # .0:  2, .1: 62, .2: 41, .3:  3
5.28  117 # .0: 23, .1: 80, .2: 14
5.30   28 # .0: 28
[download]

With just one dist (openwall-3.1, which is the most recent openwall distributeded with perl on 2018-07-03) shipping with perl-5.8.8, I'd say having a minimum of 5.10.1 is a very safe choice.

If you however really want to use a feature like s{}{}r, perlver tells me you'd need 5.14.0.