When should I add curry paste?
You typically want to bloom the spices by cooking it over high heat for some period of time.  But if you cook it for too long, you risk burning the spices.
If you're trying to brown meat, the moisture in the spices both make it more difficult (because of the spices burning first), and throw off the color to let you easily tell when it's cooked properly.
When you're making a dish that cooks quickly (like fish) or that you want to stew more than brown, I'll cook the spice paste first, then add everything to it.
In general, my procedure for using spice pastes is:

Cook down onions or other veg that needs to soften and/or brown meat (optional)
Add spice paste
Cook for a minute or so (optional)
Add whatever remaining ingredients
Cook for another minute or so
Add liquid
Simmer until cooked through

I'm actually more surprised that your paste didn't mention cooking the paste for a minute or so, or letting it cook with the vegetables before you add the coconut milk ... but it's possible that it contained an ingredient that doesn't like high heat.
It's also possible that the goal for the red curry dish is for the individual ingredients to maintain their own distinct flavor with there being a sauce at the end, rather than it being more like a stew where the flavor meld together.