Após mais investigações, eu estava de fato codificando incorretamente.
Aqui está o que eu acabei tendo, para posteridade:
return_payload = base64.b64encode(parse.urlencode(kwargs).encode("utf-8"))
h = hmac.new(secret.encode("utf-8"), return_payload, digestmod=hashlib.sha256)
resp = requests.post(
".../admin/users/sync_sso",
data={"sso": return_payload, "sig": h.hexdigest()}
headers={...}
)
E se você estiver fazendo o redirecionamento, certifique-se de usar parse.urlencode para isso {“sso”…}.