My two last examples are two different implementations of the solution you are proposing actually. You wouldn’t change urls with there two implementations.
You might still be confused with the fact that /:param1/:param2 is not actually a URL but a regex expression.
So when I say you could keep a single route called /:service/:cf you are not changing routes. You could actually call it /:mydog/:eatscats and you still wouldn’t be changing URLs.
SEO wise and old links pointing to your website like www.yourwebsite.com/plumber/france would still match /:mydog/:eatscats.
Now in the SC associated to that route you would query the database to figure out if $_GET.eatscats is a country or a function.
Now as it seems that $_GET.eatscats is a country(france) you could do two things from the SC action:
a) Redirect to /s/plumber/c/france which will match /s/:service/c/:country and that will take them to the right content page
b) Send them to a page that will show partials depending if it’s a country or a function and data specific to /plumber/france
But the users would still use /plumber/france and you keep your SEO authority for the original URL and old links working in both cases.