Better specifying requirements is good. A few comments:

-   The second argument is an error message; it is converted to a string object.
+   The second argument is an error message; it is decoded to a string object
+   with ``'utf-8'`` encoding.
 
I would write the change as
+   The second argument is a utf-8 encoded error message; it is decoded to a string object. 

I the second part (what the function will do with the arg) really needed? I think in the current version, it serves to indirectly specify that the arg in not to be a string, but bytes. If the specific encoding required is specified, that also says bytes, making 'will be decoded' redundant and irrelevant.
-------------------------------

+   a Python exception (class, not an instance). *format* should be a string
+   encoded to ISO-8859-1, containing format codes, 

*format* should be ISO-8859-1 encoded bytes containing format codes,

although I am not clear about the implications of that. Are not all format code ascii chars?
--------------------------------

I do not really like 'encoded to', but 'decoded to' is wrong. 'will be decoded from xxx bytes' is better. I think there should be a general discussion somewhere about bytes arguments and the terminology that will be used.