You won't be able to find new animals in a pet shop, but you can find them in our for sale forum on occasion. It depends upon when they breed for people. With captive bred newts you should still quarantine the new animals, but you will have much higher success rates with the new animals. Most captive bred animals are healthy and only have a few days of shipping stress compared to weeks or months. They may be a bit more expensive than your remember, but they are also going to be a lot healthier, and they should live a long time because you know what age they are when you got them.
As for other animals that go well with newts, there really aren't that many. I would never mix amphibian species, even other newt species. You could introduce a disease to an animal that may be fatally susceptible and some animals are too territorial or too different in their care requirements to be be housed together.
A lot of the same problems extend to fish. Many require temperatures that are too warm, some get too large and others have defensive morphologies that may be fatal to the newt, like spines in the fins of many catfish. The only fish I could recommend, and I really wouldn't, would be the Mountain white cloud minnow, which does well at cool temperatures and is quite small.
If you do put fish in their or more newts be aware that your tank will experience a "mini-cycle" where the biological filter must grow to compensate for the influx of nitrogenous waste. This causes a small surge in ammonia, nitrite and then nitrate just like when your tank was first cycled. There will also be more waste being produced with all the dangers that involves.
I would imagine you would do fine, considering the length of time you have kept this guy alive and well. I think it would be good if you perused
this article on food.