So finally, after some research and debugging in the past two weeks, I've managed to write a working example code that uses DIGEST-MD5 authentication with WinLDAP's ldap_sasl_bind_s function. The corresponding RFC, this answer and the official SSPI documentation gave me a lot of helps.  
Some gotchas that I ran into:
- Regardless what documentation says about the ldap_connect function: If you would like to use the ldap_sasl_bind_s function it is not just a "good programming practice" to call it first, it is necessary. Without it the ldap_sasl_bind_s returns with LDAP_SERVER_DOWN (0x51) error code.
- The valid pszTargetName (digest-uri) parameter is crucial for the InitializeSecurityContext function to avoid invalid token error. 
I hope it will help others to spend less time about figuring out how to use SASL binding mechanisms with WinLDAP.   
#include <stdio.h>
#include <windows.h>
#include <winldap.h>
#define SECURITY_WIN32 1
#include <security.h>
#include <sspi.h>
int _tmain(int argc, _TCHAR* argv[]) {
    LDAP *ld;
    int rc = 0;
    const int version = LDAP_VERSION3;
    SEC_WINNT_AUTH_IDENTITY wincreds;
    struct berval *servresp = NULL;
    SECURITY_STATUS res;
    CredHandle credhandle;
    CtxtHandle newhandle;
    SecBufferDesc OutBuffDesc;
    SecBuffer OutSecBuff;
    SecBufferDesc InBuffDesc;
    SecBuffer InSecBuff;
    unsigned long contextattr;
    ZeroMemory(&wincreds, sizeof(wincreds));
    // Set credential information
    wincreds.User = (unsigned short *)L"root";
    wincreds.UserLength = 4;
    wincreds.Password = (unsigned short *)L"p@ssword";
    wincreds.PasswordLength = 8;
    wincreds.Domain = NULL;
    wincreds.DomainLength = 0;
    wincreds.Flags = SEC_WINNT_AUTH_IDENTITY_UNICODE;
    res = AcquireCredentialsHandle(NULL, L"WDigest", SECPKG_CRED_OUTBOUND,
        NULL, &wincreds, NULL, NULL, &credhandle, NULL);
    // Buffer for the output token.
    OutBuffDesc.ulVersion = 0;
    OutBuffDesc.cBuffers = 1;
    OutBuffDesc.pBuffers = &OutSecBuff;
    OutSecBuff.BufferType = SECBUFFER_TOKEN;
    OutSecBuff.pvBuffer = NULL;
    ld = ldap_init(L"localhost", LDAP_PORT);
    rc = ldap_set_option(ld, LDAP_OPT_PROTOCOL_VERSION, (void*)&version);
    rc = ldap_connect(ld, NULL); // Need to connect before SASL bind!
    do {
        if (servresp != NULL) {
            InBuffDesc.ulVersion = 0;
            InBuffDesc.cBuffers = 1;
            InBuffDesc.pBuffers = &InSecBuff;
            /* The digest-challenge will be passed as an input buffer to
            InitializeSecurityContext function */
            InSecBuff.cbBuffer = servresp->bv_len;
            InSecBuff.BufferType = SECBUFFER_TOKEN;
            InSecBuff.pvBuffer = servresp->bv_val;
            /* The OutBuffDesc will contain the digest-response. */
            res = InitializeSecurityContext(&credhandle, &newhandle, L"ldap/localhost", ISC_REQ_MUTUAL_AUTH | ISC_REQ_ALLOCATE_MEMORY,
                0, 0, &InBuffDesc, 0, &newhandle, &OutBuffDesc, &contextattr, NULL);
        }
        else {
            res = InitializeSecurityContext(&credhandle, NULL, L"ldap/localhost", ISC_REQ_MUTUAL_AUTH, 0, 0, NULL, 0, &newhandle, &OutBuffDesc, &contextattr, NULL);
        }
        switch (res) {
            case SEC_I_COMPLETE_NEEDED:
            case SEC_I_COMPLETE_AND_CONTINUE:
            case SEC_E_OK:
            case SEC_I_CONTINUE_NEEDED:
                break;
            case SEC_E_INVALID_HANDLE:
                return -2;
            case SEC_E_INVALID_TOKEN:
                return -1;
            default:
                break;
        }
        struct berval cred;
        cred.bv_len = OutSecBuff.cbBuffer;
        /* The digest-response will be passed to the server
        as credential after the second (loop)run. */
        cred.bv_val = (char *)OutSecBuff.pvBuffer;
        // The servresp will contain the digest-challange after the first call.
        rc = ldap_sasl_bind_s(ld, L"", L"DIGEST-MD5", &cred, NULL, NULL, &servresp);
        ldap_get_option(ld, LDAP_OPT_ERROR_NUMBER, &res)
    } while (res == LDAP_SASL_BIND_IN_PROGRESS);
    if (rc != LDAP_SUCCESS) {
        printf("Bind failed with 0x%x\n", rc);
    } else {
        printf("Bind succeeded\n");
    }
    return 0;
}