Ok, you didn't mention all the other issues. Both K&N filters and an aftermarket exhaust will make the bike run leaner not richer. Anything that makes more air flow through the engine will lean out the A/F mixture, whether it is a less restrictive air filter, or a less restrictive exhaust. Both together will make it even leaner. It is very possible the previous owner did rejet the carbs, and over did it. I live at 1200 feet, have the stock filters and exhaust, and still had to turn the pilot screws out a full 3 turns to make it run right.
Remember, when you have a shop work on a bike, you will be spending most of the money on labor, not parts. I would do as much of the work as you can by yourself, though I don't advise anyone without considerable mechanical skills to remove the heads. Too much chance of messing up the valve timing.
One last thing, you said this bike was stored outside, and implied that it had not been very well cared for. I would make sure you think this bike is worth putting money and work into. There are a lot of really nice late model low mileage Vulcan 750s on my local Craigslist, for very reasonable prices, mostly due to the economy. A lot of people around here are out of work, and are trying to sell off their non essential things in order to feed their family and make their house payment. I can barely resist buying one myself. Jerry.