While I have absolutely no background in physics, I keep on getting drawn in by questions that have to do with dimensions (even if the asker didn't include dimensions, I sometimes manage to fit them in anyways). You can read a couple of my answers dealing with higher dimensions here and here.
Now that my self-plugs are out of the way, I'm going to focus on your specific questions.
How do we know that there ARE higher dimensions?
Well, that depends on your definition of higher dimensions. I have worked with, and proven things about infinite-dimensional spaces that have direct applications to the real world. In that sense (i.e. dimensions are some kind of coordinate system, roughly speaking), there are definitely higher dimensions, and infinitely many of them (even uncountably infinite dimensional spaces). However, if you don't want to simply live in mathematician land (weird) where we all imagine things, and then painstakingly describe what we're imagining using special vocabulary to make sure everyone else is imagining the exact same thing, and prefer to focus on the traditional definition of dimensions--point, line, square, cube, etc. kind of deal--then no, we can't ever be 100% certain that higher dimensions exist. That's because the only way we can prove reality is through empiric methods, which don't actually establish absolute truth. Basically, all of science/reality is unprovable, though that hasn't stopped plenty of philosophers from trying, one of the most notable being Descartes. But even if you aren't so stringent about what it means for something to be proven, there is not direct evidence for higher dimensions.
Now you (or some other reader) might be asking why--if there's no evidence for it--we roll with the theory of higher dimensions. The reason is because it provides a good model for the world. You see, when modelling, it doesn't always necessarily matter if the model matches reality perfectly. For example, economists model people's lifetime consumption choices by assuming that all people live forever (which is obviously false--sorry if I just crushed your momentary hopes and dreams) because turns out that model ends up describing what economists have observed about people's consumption better than models where people die (feel free to email me or ask another question if you want to know why this is). Similarly, even if we don't have proof for higher dimensions, the models that assume they do exist describe what we can observe about reality better than the ones that don't. Cause when it comes down to it, some information is just not available to us, so we have to guess at bits and pieces of it, and make sure those guesses don't give us results that contradict what we do know.
How many [dimensions] are there?
This depends on which theory/model you're using. If you're living mathematician/imagination land, there are uncountably infinite dimensions. If you subscribe to superstring theory, the highest dimension in the universe is 10. Again, note here that how many dimensions a model/theory either assumes or implies doesn't mean that the universe truly has that many dimensions, but it can still be a good model/theory anyways.
And how is it possible to exist in three dimensions but not in a fourth or a fifth? Nothing in our world is truly two-dimensional, is it? So how is it possible for objects to not exist in all dimensions?
To answer your first question here, it isn't. If you exist in one of the possible dimensions, you exist in every equal or higher dimension. And our world does include both one dimensional and two dimensional things. Every 3-D object is composed of infinitely many 2-D objects, which in turn is composed of infinitely many 1-D objects. However, it is definitely possible not to exist in all dimensions. In fact, unless something is 1-D, it's impossible to exist in all dimensions. For example, I am a third dimensional being. I cannot exist in either two dimensions or one dimension. However, I do exist in every dimension higher than three.
Do we know of anything in our universe that exists in more than three dimensions?
Nope. If we had definitive evidence, then we'd have evidence of higher dimensions, which as I said above, we don't.
Most of our understanding of physics has to do with how matter interacts with other matter, but matter as we understand it is only three-dimensional, right? So how might our understanding of physics have to change in order to accommodate more dimensions?
It's actually our current understanding of physics (i.e. our physical models and theories) that imply there are higher dimensions, despite the fact we don't have any hard evidence to that effect. So, if just the fact higher dimensions exist is proven, it will validate our current understanding of physics. However, if higher dimensions are proven, it's pretty likely some other weird things about the universe will come to light in the process. In that case, it's very likely we will update our models and theories to accommodate this new weird information to make the models better. Again, remember the models and theories we have aren't perfect replicas of reality; rather they describe bits of reality in useful ways. The more we understand about reality, the more we'll be able to create models to take into account those things (though not necessarily, because as previously stated, models are sometimes better with aspects that blatantly contradict reality).
How might we, humans, encounter a four-dimensional being? How would that be different from how we encounter a five-dimensional being?
Idk, man, but it'd be weird.
Can we even speculate about that?
We can speculate about whatever the heck we want. Like, we could have a full on speculating session about the complex social hierarchy of electric-blue vegan dragons if we wanted. As a mathematician, I spend considerable amounts of time speculating about worlds where things are nice and have nigh on magical properties. I get the sense you really meant, "Can we speculate accurately/reasonably about that," though. The answer to that question is no. Unless you have a really loose definition of reasonable. Seriously, we don't even know for sure if higher dimensions exist, let alone what encounters with living beings from them would look like (no pun intended).
As far as your bonus question goes, unfortunately it's been too long since I've watched Interstellar for me to have a real opinion... I seem to remember crying, though. And on that note, I'll leave you to ponder over dimensions and the art of modelling some more (or not, your choice).