This is going to be almost impossible right away, especially given the fact that Amsterdam did not grant you an interview in the first place. However, it is VERY possible to work in Paris for 2 years or even a year and then ask for a transfer to Amsterdam. I had the same exact situation and transferred to a different McKinsey office after only 1 year.
To increase your odds, try to:
1) Network with Amsterdam office colleagues (especially Partners) and
2) Try to get staffed with Amsterdam Partners and
3) Try to get staffed on Amsterdam clients (which usually overlaps #2)