When you battle, the battle moves have these stars and a percentage besides it. What does that mean?

they're attack rank indicators (you can also see them on the proficiency page of a pet).

If you're battling in the lost grove, you get a small (very small) amount of attack exp for using the move, and all moves get a small amount when you win a battle. Once the attack's rank exp hits 100%, it moves up to the next rank, improves in some way (for example, Light's Beam attack goes from dealing 100% magic damage at rank 1 to dealing 150% at rank 2), and starts the slow process of leveling up to the next rank (until you hit rank 4 which is the current cap)

So when you use the attack, the percentage increases?

fractionally. It takes a LONG time, a LOT of battles a LOT of uses. It isn't 'use the move 100 times and it ranks up' it's 'use the attack literally thousands of times to get to rank 2' (ability 1, the one that gives mana, takes the most uses, and has been calculated to take ~20k uses to get to rank 2)

There's a guide to rank exp gain here