It's looking to me like the past participle of proficisci. If this is the case, I would tend toward understanding auxilio in its military sense of "auxiliary troops" (admittedly this use is more frequent in the plural, but it does show up in the singular - and I don't think Sallust would hesitate at all to use a slightly more rare word).
"...having set out with auxiliary forces..."
Caesar has a similar construction (though he uses the plural): Caesar confisus famā rerum gestarum, infirmis auxiliis proficisci non dubitaverat, Caes. B. C. 3, 106