Assuming most of the escaping Martian atmosphere is entrained in the solar wind, it will flow outward until it reaches the termination shock, and then slow down in the heliosheath until it reaches the heliopause, currently at a distance of about 120 AU. (The actual location will change, of course, depending on things like the strength of the solar wind and the local conditions of the interstellar medium.) At this point, the former Martian-atmosphere atoms and ions ("Martian particles" for short) will be at rest with respect to the local interstellar medium (ISM) and will gradually mix into it. Since the Sun is moving with respect to the local ISM (currently at about 25 km/s), the Martian particles will gradually separate from the Sun: in a million years, they would nominally be about 25 parsecs away. (They would be diffusing through the ISM as well, but I have no idea what the speed of that would be.)
Beyond that, things start to get very fuzzy. The Sun's motion with respect to the local ISM will be changing, due to the Sun's orbit and the orbits of the ISM clouds. In addition, the ISM gas will be subject to turbulence, strong stellar winds from massive stars, supernova shock waves, and bulk noncircular motions driven by spiral arms and the occasional accreting dwarf galaxy. Differential rotation will also smear out the location of the Martian particles, since even in the absence of all the other ISM motions they will end up following slightly different orbits in the Galaxy. Some of the Martian particles may end up in the halo (e.g., if they are caught up in an expanding superbubble due the combined massive-star stellar winds and supernovae of a large star-formation region). Since stars form out of dense molecular clouds in the ISM, some will end up being incorporated in new stars.
Crudely speaking, most of the Martian particles will probably still be in the disk (some as part of the ISM, some inside stars), in a fuzzy annulus. Where this annulus is will be very hard to determine. This is because we're assuming most of the Martian atmosphere was lost in the first billion years (or less), which means that most of the Martian particles entered the ISM between 3.5 and 4.5 billion years ago -- and we don't really know where the Sun was then. Recent research has shown that stars in spiral-galaxy disks can have the radii of their orbits changed significantly -- moving inward or outward-- by interactions with transient spiral arms (and possibly also by interactions with the bar). This means the Sun might have been formed on an orbit a couple of kiloparsecs closer to the Galactic center than it is now (curent radius of Sun's orbit $\sim 8$ kpc), or a couple of kiloparsecs further away, and then moved (possibly in a series of stages) to its current location sometime between now and then.