When you say strParam: '$strToPass' that means strToPass is dynamic property but when you say mapStringParam:{key:'myKey', value:'$strToPass'}, strToPass is deeply located inside object which will no more be dynamic and it will just consider it as string.

When you want wire service to be dependent on any dynamic property like myDynamicProp, it should be directly mentioned with $ at 1st level:

myApexParam: '$myDynamicProp'

So, you can change your JS as follows:

@track mapStringParam = { key: 'test value' };
@track strToPass = 'test value';

@wire(myApexMethod, {strParam: '$strToPass', mapStringParam: '$mapStringParam'})
    wiredInitData({ error, data }){
    if(data){
        this.data = data;
    }

Whenever you change mapStringParam.key, it will re-invoke this wire service. else if(error){ this.error = error; } }

Added based on comments

You need to modify the dynamic property mapStringParam in change handler of strToPass so that wire service is invoked whenever dynamic property is changed. Below is code:

@api
get strToPass() {
    return this._strToPass;
}
set strToPass(value) {
    this._strToPass = value;
    this.mapStringParam = { key: this.strToPass };
}

@wire(myApexMethod, { mapStringParam: '$mapStringParam' })
wiredInitData({ error, data }) {
    if (data) {
        this.data = data;
    } else if (error) {
        this.error = error;
    }
}

OLD Answer

When you say strParam: '$strToPass' that means strToPass is dynamic property but when you say mapStringParam:{key:'myKey', value:'$strToPass'}, strToPass is deeply located inside object which will no more be dynamic and it will just consider it as string.

When you want wire service to be dependent on any dynamic property like myDynamicProp, it should be directly mentioned with $ at 1st level:

myApexParam: '$myDynamicProp'

So, you can change your JS as follows:

@track mapStringParam = { key: 'test value' };
@track strToPass = 'test value';

@wire(myApexMethod, {strParam: '$strToPass', mapStringParam: '$mapStringParam'})
    wiredInitData({ error, data }){
    if(data){
        this.data = data;
    }

Whenever you change mapStringParam.key, it will re-invoke this wire service. else if(error){ this.error = error; } }