Why does an aircraft as big as the Airbus A400M use turboprops?
Both aircraft seem to have the same purpose


Not entirely.

The RAF see the C17 as a strategic airlifter, the A400 is seen as a tactical airlifter replacing the turboprop C130.  

Strategic airlifters are more likely to make longer, higher-altitude journeys. Where jets are more fuel efficient. They are more likely to operate between airports with concrete runways where FOD is less of an issue. 

Tactical airlifters are more likely to make shorter, lower-altitude journeys of the sort where turboprops are more efficient. They are more likely to operate between smaller airfields where FOD may be more of an issue.

References:


ThinkDefence
Airbus
RAF




Some random internet website alleges the fuel costs in \$ per Nautical mile are 19.63 for A400 and 88.14 for C17. They don't say for what mission profile. At a minimum, this illustrates that there is some motivation for matching engine types to expected mix of mission types.







The similar sized AN-70 also uses turboprop engines, illustrating that this choice is not unusual for this sized aircraft.