REF: Categorical.fillna match patterns in other methods
Also:

- always return a copy even if there is nothing to fill
- validate the fill_value even if there is nothing to fill
what is the visible user change here? > what is the visible user change here?

A couple of exception messages changed (see changed tests), always returning a copy even if a no-op, always validate fill value even if no-op (see OP, xref #36466) Possibly closes #19705 cc @TomAugspurger  whatsnew added + green nice code deletion!