I'm not a native speaker, but in my experience with PT-BR, the difference is like this:
mudar = to change (the person or object changes its form, status, position, etc)
mexer = to move (the person or object physically moves)
Both could be obliquely interpreted as "move" or "change" in English, but it seems to me that the basic difference is that mexer is for movements or changes that happen in the physical world and mudar is for abstract movements or changes.
He changes - positive statement, simple present tense verb He does change - positive statement with emphasis on verb He does not change - negative statement requires the use of do/does
Does -3rd person singular present tense Do - Present tense for all other (1st person singular and plural, 2nd person singular and plural, 3rd person plural
He changes - only one verb so it conjugates to match the subject Does/does not change - 2 verbs, only the first verb conjugates.