I'm looking into developing an XSLT 2.0 stylesheet [...] A brute-force
solution is easy enough; just string together replace() functions
[...] This type of brute-force approach would string together dozens
(possibly hundreds) of these rules to account for all possible sandhi
modifications. That seems inappropriately crude because the rules
actually apply to *classes* of letters [...] What I'm groping for,
then, is an elegant rule-based function that lets me write a small
number of rules by defining classes of letters to which they apply,
something like "after 'S', 'Z', 'C', 'St', and 'Zd', 'y' is replaced
by 'E'." [...]

I think the key technology to solving this problem are regular
expressions, which do not require the use of XSLT, but are available
in XSLT 2.0. Specifically, you may be interested in character classes.

Finally, there is a slightly less brute-force approach where I would
create not just one paradigm of basic endings plus rules to change
them in certain circumstances, but several paradigms that already
incorporate the changes, and I would look at the last stem consonant
or two and select the appropriate paradigm. Is such a "selection"
approach more appropriate for this type of problem than the
"modification" approach I've been contemplating?

That depends on your rules' ability to select the best paradigm among
all those you have generated. To me, it doesn't sound more intuitive.
In all the languages I've learnt, morphological correctness is derived
from stem forms, like infinitive, 1. Sg. Present, 1. Sg. Perfect, etc.
You do not usually determine the correct form by eliminating all
incorrect forms.