I just finished the first campaign mission (Griffin Bane) on Normal difficulty and apparently my completion score was 12250 (46%). The tooltip says I can
Increase [my] score by completing quests, picking up resources and artifacts, defeating neutral packs and heroes and controlling capturable buildings at the end of the map.
However, it's not that big a map. Far as I know, I visited every corner, completed every quest, beat every enemy and gathered all available resources.
What am I missing?
I can only guess at what you might need to do.
Did you avoid any fights with neutral creatures? Did you defeat every enemy hero? Did you capture every town? Did you own all artefacts and all heroes and all units that were purchasable from your cities?
Perhaps it counts against you if an enemy player kills a monster or uncovers some territory first? I wouldn't expect that 100% is possible on normal difficulty anyway. Perhaps you need to play perfectly in the highest difficulty mode to get higher completion scores.