Which is correct/sounds more natural?
He tries to make (a) space by shoving my bag away.
Both are acceptable but mean slightly different things. "To make a space" implies that a specific open area is being made for a specific purpose or object in a particular location. "To make space" is more vague and relaxed and denotes the creation of more available space in general. In some cases one is more appropriate than the other, and in other cases both would work. As a native speaker my ear has a preference for "to make space" so I'd prefer that form if there is overlap.
I think it is probably more idiomatic to use:
to provide space for someone or something.
- Make room for Sam. He needs a place to sit. Can you make room for this package?
(The Free Dictionary)
See also Google Books for make room, vs make space, make a space.