It is my understanding the best evidence we have for Sgr A* being the black hole at the center of our galaxy is the incredible velocities of the stars orbiting around it. But wouldn't the stars similarly orbit the center of mass of the Milky Way? Not nessesarly needing there to be a black hole there?
Objects orbit around their barycenter. The barycenter always is closer to the more massive object. If the difference in masses is very great, it can be inside the more massive object (such as the Earth/Sun barycenter being inside the Sun).
But the barycenter also can be outside any one object in a gravitationally bound group. If there are many objects and they are roughly the same mass, one would expect objects in the group to interact with one another in more complicated and difficult-to-predict ways than if there were a single massive object at the core.
Such is the case in Globular clusters, which are spherical groups of stars that may in some cases orbit their group barycenters. Predicting or even studying the trajectories of individual stars in these clusters is complicated by the n-body problem, the vast computational resources necessary to plot gravitational interaction of 3 or more objects. Stars in globular clusters have been observed following unusual paths that may change shape with time.
The motion of stars around the galactic core of a spiral disk like the Milky Way is more regular than the motion of stars in globular clusters. This is one indication that a single massive object is the attractor at the center of the Milky Way.
Gravity obeys something called Gauss' Law, which states the gravitational acceleration is proportional to the mass enclosed. So even though the total mass of the milky-way is very large, when you're very near the center, the mass effecting gravity is much smaller. The gravity from everything outside of the enclosed area ends up (roughly) canceling out. The same applies to other objects, like the sun or earth: if you were to tunnel down into either, the gravitational acceleration would decrease.