Mul/Div are part of the M extension, which any non-trivial/tiny embedded implementation have. The chip in this link for instance supports this extension. Likewise AES and SHA could be supported in a crypto extension.
REP MOVS/STOS is not optimized at all. The Architectures Optimization Reference Manual says that SIMD instructions are faster. The only reasons to use REP MOVS/STOS are to deal with unaligned parts of the data and to not have startup cost from checking if SIMD is available via CPUID when you have only a few bytes. Further the intel manual tells you to not use the other string instructions at all.
> if by definition all instructions already run in one clock cycle
Then you are using a different definition of RISC than RISC-V does
> the key difficulty here being that recognising and combining instruction sequences is much harder than decoding a single instruction to a sequence of uops or dispatching it to hardware internally.
Why is that supposed to be more difficult? Matching combinable instructions is trivial.