There is a permanent market in Paphos Old Town.
You could probably walk there from most areas of Kato Paphos.
From the harbour head up the hill (away from the sea), go straight through the traffic lights at the Tomb Of The Kings road, carry on for about 200 yards, turn left and there it is.
There is a large pay and display car park adjacent to the market.
There are no other markets in Paphos, although the seafront near the harbour is the next best thing. It's as tatty as you can get with stalls and shops on both sides of the road.