I agree that you may be suffering from Imposter syndrome. That is, reading your post I see no evidence that you aren't prepared, and in fact, I see several pieces of evidence that you are prepared. Despite your accomplishments, you are underconfident and do not realize that many of your peers are going through the same struggles as you are; you see these as failures when they are perfectly normal even for someone with a high level of preparation.
I went into a masters program. I ended up doing really well (3.9GPA) and gained a lot of confidence and expanded my knowledge.
This is a good sign that you are a strong candidate, and well-fit for a PhD.
I ended up selecting a foreign university
Not only did you select it, the admissions committee selected you. Admissions committees are usually very good at what they do, and they will not admit a candidate who they believe is underprepared. They are aware of your background, including the master's program you went through, and they believe you are an ideal candidate for their program.
Now that I am about 6 months in however I am seriously questioning the quality of the master's program I was part of.
Different programs do vary in what material they cover, but the far more important factor in a PhD is not your specific set of knowledge, but your ability to learn, your ability to deal with unfamiliar material, and your motivation, creativity, and insight. It is possible your master's program didn't cover some things that others' covered; but it is also possible you are imagining at least part of it. Regardless, you shouldn't be surprised if it takes a lot of difficult work to learn all the new material!
I spend hours and hours spinning my wheels reading and trying to understand papers, feeling like I just don't know the background I need to.
This is what doing a PhD is like for everyone. The reality of academic life is that you often are thrust into new areas that you have no experience in; you have to learn to swim over and over again, every time you take a new class, every time you start working on a new research problem. Contrary to what you think, this doesn't sound like a red flag that you are underprepared.
I have somewhat discussed these concerns with my advisor but they seem confident that everything is fine.
This is the biggest sign (to me) that you have imposter syndrome: your advisor is still confident in your progress, but you aren't. Your advisor has seen a lot of students and they should be able to tell better than you about the situation.
I also find that now that I am here the project I am part of is much more applied than I had anticipated and I am unsure about if this will evolve to more closely match my interests over time or if this is just another indication of a poor match.
I am not sure how this could be an indication of poor match. You should talk to your advisor about this, though; your interests are important. See if you can figure out what aspects of the project you would be more interested in pursuing (maybe the less applied aspects). Recognize that it is common for people who join a new program, working on learning new ideas, to feel that everything is unfamiliar and to have a negative reaction to that.
I am not sure what to do. Is this a normal experience?
Yes, it is normal: I have heard the same things from many very strong students.
If it truly is not a fit for me at my current level of knowledge, what are my options?
You have been admitted, your advisor is confident you are doing well, and you have a strong background, so reconsider why you think it is not a fit. If there are things you are not prepared for, then you should consider taking the time to slow down, relax, and learn those things. It may take some time; don't worry.
Also, take some time for yourself. Make sure to look for a social group that you can find a sense of belonging in; it makes a world of difference. Consider seeing a therapist to discuss your fears of not belonging and not being ready.