First, instead of a headband of vast intelligence, I recommend the circlet of speaking (4,800 gp; 0 lbs.), which grants an animal wearing it the ability to speak 1 language yet doesn't increase the animal's intelligence. Although slightly more expensive than the cheapest headband, the circlet is, in many ways, superior if you want a talking animal that can still be trained; it neatly sidesteps the intelligent animal's language issues detailed below. That said...

Yes, were an animal to wear a headband of vast intelligence +2 et al. that animal could learn a language were its Intelligence score to have gone from 1 or 2 to at least 3

Such an animal could learn to understand a language but couldn't learn to speak. The section on Intelligent Animals says that

Increasing an animal's Intelligence to 3 or higher means it is smart enough to understand a language. However, unless an awaken spell is used, the animal doesn't automatically and instantly learn a language, any more than a human child does. The animal must be taught a language, usually over the course of months, giving it the understanding of the meaning of words and sentences beyond its trained responses to commands like "attack" and "heel."

Even if the animal is taught to understand a language, it probably lacks the anatomy to actually speak (unless awaken is used). For example, dogs, elephants, and even gorillas lack the proper physiology to speak humanoid languages, though they can use their limited "vocabulary" of sounds to articulate concepts, especially if working with a person who learns what the sounds mean.

So the vague description above of how to teach an intelligent animal language all but says not to bother trying. Further, the most obvious way of improving an animal—taking the animal on adventures so it can gain XP—isn't an option, either, because animals, like most NPCs (cf. the feats Leadership and Squire), just don't earn XP.

Thus while the intelligent animal has the potential for language—all it would take is but 1 rank in the skill Linguistics for the animal to understand a language—, the intelligent animal lacks the ability to gain that rank. It's stuck with what it has.

However, to use what it has, the creature can employ the rules for retraining its skill ranks. By spending a paltry sum and as long as a several weeks, a creature can allocate its accumulated skill ranks differently. For an intelligent animal, this lets it put that minimum 1 rank in the skill Linguistics and understand a language.

Example
A common cat has 1 Hit Die and while wearing a headband of vast intelligence +2 an Intelligence score of 4. The cat murders a family of commoners and takes the family's treasure, as is a cat's wont. The cat spends 50 gp and 5 8-hour work days avoiding strenuous activity and, afterward, reallocates its skill rank from the skill Perception to the skill Linguistics, therefore learning the language of its choice.

Unfortunately, as they have no starting language, most animals are barred from using the retraining rules to learn a New Language independent of their ranks in the skill Linguistics because

Each language [gained through the New Languages section of the retraining rules] requires a trainer who shares a language with you and knows the language you want to learn, or a book written in a language you know that explains the basics of the language you want to learn.

Emphasis mine, and these rules make me sad. However, the DM could allow a trainer with the ability to speak with animals for 8 hours a day and who was willing to do so be an intelligent animal's language trainer. Extending the duration of a speak with animals effect from its typical 1 min./level to at least 8 hours is not impossible (e.g. a friendly high-level character's familiar that can both speak a language and speak to others of its kind, a creature with the animal domain and the pelt of the beast, feral speech a la wizard or witch). This New Language retraining, were it available, would cost the intelligent animal 200 gp and occupy both the intelligent animal and its trainer for 20 8-hour work days that must be otherwise absent of strenuous activity.¹

Strangely, an animal with an Intelligence score of 1 or 2 can put ranks in the skill Linguistics, doing so through retraining as described above or just using its native skill ranks.² The animal, however, still isn't "smart enough to understand a language," so what, exactly, these ranks in the skill Linguistics do for an animal is unclear. (Animals that are also animal companions have a skill list that prevents the animal companion from putting ranks into some skills at all.³ Such a creature can't put ranks in the skill Linguistics until it has an Intelligence score of at least 3.)

Yes, a headband of vast intelligence +2 et al. that's imbued with the skill Linguistics and that raises an animal's Intelligence score to at least 3 grants the animal the ability to understand a number of languages equal to the animal's Hit Dice.

Such languages are probably picked by the item's creator, although this isn't entirely clear. An animal wearing such an item wouldn't need to "be taught a language, usually over the course of months," nor retrain as described above. Such a creature still can't speak, however.

No, a typical thrush or typical raven (or parrot) wearing a headband of vast intelligence +2 et al. that learned a language would not be able to speak that language.

Only when these creatures become familiars do they gain the supernatural ability to speak but 1 language. In fact, only if further effects permit is such a familiar ever able to speak more than the 1 language picked when the familiar was first gained. While the familiar may be able to understand other languages (e.g. bonus languages from a high Intelligence score, its master's Linguistics skill, a headband of vast intelligence +2 et al. imbued with the skill Linguistics), the familiar will remain unable to speak those languages.

However, it's a reasonable house rule to allow a familiar with the supernatural ability to speak 1 language to speak, instead, any language it knows.

¹ Undoubtedly, there's a sitcom pilot being pitched right now about a good-hearted but down-on-his-luck wizard with the arcane discovery feral speech who teaches Common as a First Language classes to wealthy, murderous cats at the local night wizards' school. Attention, Networks: I will pay real money to watch this show.
² An animal's class skills are Acrobatics, Climb, Fly, Perception, Stealth, and Swim. Thus the animal can put ranks into the skill Linguistics, but won't get the bonus that comes from the skill being a class skill.
³ "Animal companions can have ranks in any of the following skills: Acrobatics* (Dex), Climb* (Str), Escape Artist (Dex), Fly* (Dex), Intimidate (Cha), Perception* (Wis), Stealth* (Dex), Survival (Wis), and Swim* (Str). All of the skills marked with an (*) are class skills for animal companions. Animal companions with an Intelligence of 3 or higher can put ranks into any skill."

Sorta

There are things you can do make large battle scenes more tolerable in PF/3.5, such as;

1. Grouping Attacks - Similar units with similar attacks are grouped into 'volley' attacks that are dodged with either a saving throw, or are fewer attacks that deal more damage.
2. Placing Fights - creating larger 'maps' for fights with terrain that separates groups of combatants allows the players to use terrain and selectively engage enemies, turning a 'large fight' into a series of smaller fights.
3. Treating Groups of Enemies as a Single Creature. Roughly what the DMGII's 'Mob' template does, treat a group of weaker creatures as a single creature with it's own hp and attacks. HP being whittled away kills members of the group, but it still only has one set of stats (although probably a Swarm attack).
4. 'Battle', treating weak enemies as a terrain effect. They're rough terrain and deal environmental damage to the party, but they're not units with hp - by moving through them, the party is killing/fighting through them, but the party's real enemies and real goals in the scene are unrelated to them so they don't roll dice or do more than hinder the party. Like orcs in a LOTR battle, the party spends it's actions shooting down oliphants and stuff, killing orcs happens 'during' their other actions.
5. Waves, enemies come as relatively discrete encounters with a time pressure of if you don't wipe them out the next wave is going to arrive. In this case, the papermancer would be origami'ing new monsters as the party cut down the ones he has already made, and doing other things like sending waves of sharp-edged paper birds through the group, sending paper streamers in blue hues to 'flood' the party and ruin their footing etc (you can refluff a lot of spells to be origami).

But you shouldn't be hanging everything on a single battle anyway

Any good villain is foreshadowed. Paper mantis assassin striking the party in the night, learning about the man who wears a white paper mask and kills with paper knives, thugs wearing paper armour with paper swords (that are made from scrolls, and the thugs can activate them), an ally of the party being killed a paper chain that climbs singing into his mouth and chokes him to death at a dinner party, the climactic fight at the hideout alongside their allies, the papermancer boarding a paper dragon to escape, the final confrontation on the mountain where he defends the diggings of the Jade Lotus society's attempt to resurrect a dead god, defeating the papermancer who fights to the very last with no advantages to defend a man who isn't worthy of that loyalty, thereby giving the PCs yet another reason to hate Marcus Stein, aka Xaoyao Luyfu, the Hidden Master of the Cult of the Jade Lotus.

Etc etc. You introduce, you create importance, you cause confrontation, you (hopefully) escalate the confrontation, and then you add twist to season, either twisting to make the character relatable or sympathetic or to make them even more horrifying than the party ever dared suspect.

That's what makes a memorable villain. Large fight scenes can be story-required, like if you foreshadow that the papermancer if given time can create a paper-army, and then the party gives them time, but they do not create memorable villains or highlight interesting story features.