This text is also present in the 5.005_03 documentation.
Even the documentation that came with perl5.004 includes those two paragraphs:
m Treat string as multiple lines. That is, change "^"
and "$" from matching at only the very start or end of
the string to the start or end of any line anywhere
within the string,
s Treat string as single line. That is, change "." to
match any character whatsoever, even a newline, which
it normally would not match.
Although it lacks the followup explanation of the interactions between /s, /m, and $*.
The original poster must have a very old version of Perl. Complaining about a lack of documentation in such an old version of Perl is pointless. The problem was found and fixed years ago; the solution is to upgrade.