The preposition you're looking for is "during".
It was during the week of your birthday that Tom went to Paris.
Note that it should be "that" not "when". This sentence order is a bit odd but it'd be considered acceptable.
In your second phrasing, you might alternatively consider using "over" instead of "in".
Tom went to Paris over the week of your birthday.
Tom went to Paris during the week of your birthday.
That being said, you don't really need either of them in this construction:
Tom went to Paris the week of your birthday.
Though this lacks total clarity... it could simply mean that he departed sometime during that week but not that he was gone for the entire week.
Another way you could say it is
Tom was in Paris the week of your birthday.
This is clear, concise and means that he was gone that entire week. All of the options above are good for your example, though.