This is a rather general question. I started figuring out how Texture Painting works, the second time now to be honest. I don´t understand why to bother and mark certain seams, when you can just mark all edges at once and unwrap them afterwards. It worked last time, when I was just using an existing texture without trying to paint. So what would be wrong about marking all edges as seams?
If you want a more simple approach to getting started with Texture Paint, then consider using 'Smart Unwrap' from the Unwrap menu - no need to mark any seams with this option, and you can get on to painting. If you decide you really need a better map, then you can create a second UV map with the correctly marked seams and then bring in the paint from the previous mapping to a new image with the Clone Tool using the second correct mapping.