Abstractly, adding an MVP level player and offensive GOAT to a 50+ win team should give you good results, yes. On the granular level, not sure it is totally clear cut.
First, that pair has to work. I think it is fine to conclude based on Robinson’s skillsets that they would, but it is hardly an absolute guarantee. For the exercise though, we will say it does.
Then you look at how the Spurs lost in this period. In 1994, their offence takes a massive hit against the Jazz (down nine points per 100 from regular season) and their defence allows the Jazz to improve their offence by two points per 100. Nash does not fix that defence, so does he make up ten points of offence? Big number, but in the sense that Spurs team in particular had poor creation without any replacement for Avery Johnson’s exit, Nash seems to fix a lot of that. With league best offensive rebounding from Rodman (who was there in 1994 despite what some of you are suggesting), a good wing shooter in Dale Ellis, and a complementary big in David Robinson, that sounds like a potent offence to me. If they can best the Jazz then I absolutely think they can push for a title, and if they somehow lose to a one-man Rockets team then Hakeem really is the GoAT centre.
In 1995, they should beat the Rockets. It was already a competitive series, and now their offence is receiving a notable boost. Kenny and Cassell are not slowing down Nash, and then in the Finals, Shaq is getting torched. Oddly enough, I feel a lot better about this year than I do about 1994: the benefits of avoiding your worst matchup!
Speaking of which, the story is similar in 1996 as it was in 1994… except the Jazz perform even better on offence and the Spurs perform even worse. In their main rotation, they lost Rodman, replaced Dale Ellis with a similar archetype in Chuck Person, and had both Sean Elliott and Avery Johnson back in the fold. So right away we can partially see the consequence of going from top in the league offensive rebounding to near bottom of the league

, but also, with Avery being there, the rate of improvement with Nash is theoretically lessened. I say theoretically because with Nash they actually do spout a four-out lineup around Robinson, and that sounds possibly more lethal in Nash’s hands than 1994 did… but maybe I am discounting the sheer value of Rodman’s offensive rebounding.
Regardless, with the Jazz performing as they did, this seems like a tougher ask even before getting into the Bulls matchup…
…
but what if the Spurs could just dodge the Jazz entirely? The Jazz were a consistently rough matchup for the Spurs in this period. Against other teams, they might fare a lot better. In 1994, facing the Jazz is effectively inevitable. In 1996? Well, if the Spurs and Sonics swap seeds, as they should with Nash, then Sonics/Jazz becomes a second round matchup, and the Jazz lost that one. Beating the Sonics is no easy feat (unless you are an 8-seed

), but they probably give the Spurs fewer troubles than the Jazz do. Those who are lower on Nash (or inordinately high on all Jordan’s competitors…) might argue Payton would eat Nash alive. Personally, I do not see it, but the Bulls matchup that would follow is pretty tough to call (always encouraging when you cannot defend Jordan), so here we can fairly say that a title would be questionable at best.
All told, giving them a title in 1995, probably a title in 1994, and a small chance at a title in 1996.