Mulch early and keep it maintained. Its much easier to mulch right after you plant and make sure it doesn't wear thin, than worry about weeding. An occasional weed may pop up through your mulch but these are easy to see and pull.
If it looks out of hand right now.....weed eat and THEN mulch. Newspaper is great but you have to cover it with grass clippings, straw, hay, etc. or it will dry up and blow around in the dry times.
I have permanent pathways also and they are great. I use old hay to mulch and it does well. And, no, it doesn't create more weeds nor does it grow hay in my garden.