The Shulchan Aruch 46:3 says that one may enter if they are covered either with something that has a tefach or a covering that is not designated specifically for the tefillin (i.e. a suitcase)
היה לבוש בתפילין והוצרך לבית הכסא בלילה או סמוך לחשיכה שאין שהות להניחם עוד אחר שיצא לא יכנוס בהם גלולין בבגדו ואפי' להשתין מים בבית הכסא קבוע אלא כיצד יעשה חולצן ומניחן בכלי אם היה בו טפח או בכלי שאינו כליין אע"פ שאין בו טפח ואוחז הכלי בידו ונכנס:
If one was wearing תפילין and he needed to use the bathroom [and it was] at night or close [enough] to night where there would not be enough time to don them again after he exits [from the bathroom], he should not enter with them wrapped in his garment, even to urinate in a permanent bathroom. Rather, what should he do? He should remove them and place them in their container as long as it has a tefach [of space inside it], or in a container that's not its [designated] container even if it doesn't have a tefach [of space inside it], and then hold the container in his hand and enter [the bathroom]
The MB in 47:23 says that the reason is to avoid people stealing the tefillin, which is your case.
Halachapedia brings the following psak from Rav Shachter:
If someone is in the airport and he needs to go to the bathroom if he can leave his tefillin with another Jew he should leave it with him outside the bathroom, but if not he should bring the tefillin to protect it