I looked at your screen shot and explanation but i'm not quite sure that the root cause of your issue is related to a charset issue. There might be another explanation.
If you look at the SAMLResponse value from the server response. The value is sent in multiple lines i.e with carriage return.
And if you look at the request when the value is sent, it seems to be sent within a single line. Could you confirm that?
Did you compare that SAMLResponse value on both recorded and replayed requests to see if that value was sent in the same way?
I mean when you extracted that value, did you also extract the carriage returns and so having them sent in the request which could lead to such error on server side not understanding the content of that value?
the SAMLResponse value not contain any carriage return, it is like a table format, you can see attached files, I diff those two value, they are total same