(I don't think your cheese/ham sandwich thing is a very good example for you :) because they are both sandwiches - they do look the same and they're both for the same thing!! That sounds like an argument I should use)
But to be more serious. It's a very good point (indeed the central point) - is art a new concept and when I sit down to carve a horse on a bit of bone, am I doing something fundamentally different to someone in the ice age doing the same thing. Personally, I don't think I am. Personally, the fact that I (think I can) see that the IA person closely observed the horse to produce something that captures a horse - I feel like I recognise that process from my own art making.
Whatever reason they drew the horse (for fun, for mysterious hunting reasons, for totem animal reasons, whatever it might be) - they still had to go through that same process of observing and capturing, and so there is something in common with their art making and my 21st century art making. That's how I can recognise that those people who painted in the caves were effing good artists.
If you say what they did isn't art, or totem poles aren't art, or african tribal objects aren't art - you're pushing a wedge between your culture and other people's cultures, between you and your perception of other people. I think that's quite dangerous really, it implies some cultural superiority stuff (which I'm sure you don't subscribe to), you're saying we have Art but they don't have art, they just have making things that look a bit like art to the untrained eye.
Moore and Picasso were inspired by images and objects from other times and other cultures. But they weren't copying them, they were taking inspiration from them to free their minds about what art could be. It didn't have to be the medieval european standard of realism. Things that aren't "realistic" can capture the essential of something even though they aren't carbon copies of them.
I think you're saying that your definition of art is something that's made by an Artist, to be Art. Maybe, that it must be Art without having another function? But those Japanese bowls, they're not rough objects, they're made by craftsmen however rustic their hands, and those people were following very specific aesthetic rules - they knew what they were doing, and they did it deliberately (even if those objects became Useful Objects, not just decorative objects).