This is indeed a doc problem, although there was some discussion of working toward a method rename.  See issue 8047 (but be prepared to read a novel to understand why tostring returns bytes...)  The doc for 3.2 is slightly clearer, but both 3.1 and 3.2 could be made clearer by referring to an 'encoded byte string' rather than just an 'encoded string'.  (An encoded string has to be a byte string, but that isn't obvious unless you've dealt with encode/decode a bunch.)

Technically this could be closed as a duplicate of issue 8047, since that issue proposes that the API fix (which would include the doc change) be backported to 3.1.  But no one has proposed a patch there, so at a minimum the 3.1 docs should be clarified.