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;
        }
    }