So, at the end I found the answer and I'm going to share it with the audience, in case someone may have the same issue.

But before I provide code, a few more words about SOAP service. 

The SOAP service has just one  method - Test. It accepts a string and returns another string. That's it. I then created a WS Policy via Wizard, this policy is using SAML Authorization with X.509 Certificates. (no ws addressing,  no body / token protection, and recipient token using X.509 credentials to keep my example simple)

I then generated a SOAP client, based on WSDL produced by the above service.

and here is the code:

Class WSC.ClientTest Extends %RegisteredObject
{

/// d ##class(WSC.ClientTest).Run(2)
ClassMethod Run(pValue As %String = 0)
{
    set tClient=##class(WSC.SecureDemo.MySecuredServiceSoap).%New()
    set tClient.SSLConfiguration="SELF-MASTER"
    
    /*******************************************************************
       In real life, we would retrieve a SAML Assertion token from 
       an IDENTITY PROVIDER - IdP - and just pass it to the web service.
        
       The WebService (SERVICE PROVIDER / SeP) (unauthenticated 
       or using a technical account on Cache server side) 
       would need to retrieve the SAML Assertion from SOAP Header 
       and perform its validation
    *******************************************************************/
    
    // !!! PLEASE REMEMBER TO DELETE A WS-POLICY CONFIGURATION GENERATED FOR WS CLIENT!
    
    
    /***********************************************************
    *    This is a dummy code to construct a SAML token...      *
    ***********************************************************/
    set tCred = ##class(%SYS.X509Credentials).GetByAlias("SAML-DEMO","norway01")
    
    // Create the SAML Assertion token object - this is just a form of X509 certificate
    #dim tSamlAssertion As %SAML.Assertion = ##class(%SAML.Assertion).CreateX509(tCred)
    set tSamlAssertion.IssueInstant = $zdt($h,3,,3)
    
    // in real life we would receive this data from IdP !!!
    #dim tName As %SAML.NameID = ##class(%SAML.NameID).%New()
    set tName.NameID = "https://DESKTOP-Q224QPV"    // saml token issuer, in this case it's me, my computer :)
    set tSamlAssertion.Issuer = tName
    set tSub = ##class(%SAML.Subject).%New()
    #dim tName2 As %SAML.NameID = ##class(%SAML.NameID).%New()
    set tName2.NameID = "daniel.kutac@intersystems.com"
    set tSub.NameID = tName2
    set tSamlAssertion.Subject = tSub
    #dim tAuthSt As %SAML.AuthnStatement = ##class(%SAML.AuthnStatement).%New()
    set tAuthSt.AuthnInstant = $zdt($h,3,,3)
    
    
    // SAML conditions - make sure SAML token is not valid too long...
    set tNow=$h
    set tConditions=##class(%SAML.Conditions).%New()
    set tConditions.NotBefore=$zd($p(tNow,",",1),3)_" "_$zt(($p(tNow,",",2)-30),1)
    set tConditions.NotOnOrAfter=$zd($p(tNow,",",1),3)_" "_$zt(($p(tNow,",",2)+900),1)
    set tSamlAssertion.Conditions=tConditions
    
    // Attribute statements
    #define AddAttribute(%key,%value,%nf) set tAttribute = ##class(%SAML.Attribute).%New() ##continue
        set tAttribute.Name=%key ##continue
        set tAttributeValue = ##class(%SAML.AttributeValue).%New() ##continue
        set tAttribute.NameFormat = %nf ##continue
        do tAttribute.AttributeValue.Insert(tAttributeValue) ##continue
        do tAttributeStatement.Attribute.Insert(tAttribute)
    #define AddStringAttribute(%key,%value,%nf) $$$AddAttribute(%key,%value,%nf) Do tAttributeValue.SetString(%value)
    #define AddElementAttribute(%key,%value,%nf) $$$AddAttribute(%key,%value,%nf) Do tAttributeValue.SetElement(%value)
    
    set tAttributeStatement=##class(%SAML.AttributeStatement).%New()
    $$$AddStringAttribute("name","Daniel Kutac","")
    $$$AddStringAttribute("network_id","kutac","")
    $$$AddStringAttribute("division","Sales Organization","")
    do tSamlAssertion.Statement.Insert(tAttributeStatement)
    
    /************************************
    *     End SAML Assertion data        *
    ************************************/

    // add SAML Token to SOAP Header
    do tClient.SecurityOut.AddToken(tSamlAssertion)
    
    // add WS timeStamp, this is needed by WS Security policy
    set tTS=##class(%SOAP.Security.Timestamp).Create()
    do tClient.SecurityOut.AddSecurityElement(tTS)

    // this would be, in real life, a technical account, or even unauthenticated CSP application
    set tUToken=##class(%SOAP.Security.UsernameToken).Create("kutac","xxx")
    do tClient.SecurityOut.AddSecurityElement(tUToken)
    
    // response has - per policy - signed body, we only display result, if signature is valid
    #dim e as %Exception.AbstractException
    try {
        write !," result: ",tClient.Test(pValue)
    } catch (e) {
        if $ZERROR["<ZSOAP>" {
            w !,"SOAP FAULT ERROR:",!
            d $System.OBJ.DisplayError(%objlasterror)
        } else {
            w !,"Other error:",!,e.DisplayString()
        }
    }
}

one more comment: you may need to implement OnPreWebMethod() method in the SOAP service where you validate incoming SAML assertion token.