Given the parameters of the questions, the answer is: Not any time soon, if ever, not realistic.
You refined the question to point out that you are not interested in faster fortification alternatives, and a palisade is in place already anyway. What is wanted now is a "nice stone wall" 10x4m, and 4km long. There's a few hundred workers available. I will assume, in your favor, that a few hundred means 1,000.
A stone wall of these dimensions weights approx 440,000 tons. Even assuming it's only a rough (not-nice) stone wall or a "nice" stone wall exterior filled with rubble, the sheer weight is totally no-go given a limited time frame and medieval technology.
A thousand people would have to move around 440 tons per capita (with medieval technology, that is mostly their hands, animals, carts, and treadmills). 440 tons is an awful lot of weight to move around for one person, unless the distance is negligible. If you assume 2 years of time to do the job, that's over 600kg per day to be moved from quarry to worksite, and lifted up, 5m on the average for a 10m high wall. Not counting anything else, that alone is very harsh already.
(Fun fact: I've actually done that haul work once, 25 years ago, so I kinda know what I'm talking abut. 125 packs of tiles ~20kg each, 3rd floor, 3 young, healthy, muscular males working = 40+ trips per head. Takes all day. The first three trips are easy going, then it gets more and more exerting. After 20 trips, you wish you were dead. A week later, you still can't walk without pain. Now imagine doing that for 2 years straight, no holidays, and as someone in typically-medieval health condition.)
Also consider that a "nice" stone wall with more or less regular blocks will need masons cutting stone, which both increases the amount of material needed, and takes time. With medieval techniques, a skilled mason can cut 2-3, if pressed hard maybe 5 shoebox-sized blocks per day.
If one is very optimistic and assumes all your 1,000 workers are skilled masons, all of them working at super killer top speed, and assuming a rubble-filled wall with only a nice exterior, that's something like 200+ blocks per meter needed, or upwards of 800,000 blocks for a 4km wall.
That's two years of work just for the stonecutting, assuming the materials just magically appear in-place when they need them, and blocks are magically placed on the wall and such. No cranes needed, nor people to operate the treadmills, nothing of that kind, all that is assumed to just happen by magic. Realistically, you can at least double the number of workers needed (try and work in a treadmill for 8 hours per day!).
If you assume your nice stone wall being more massive, not just rubble-filled exterior walls, then multiply that figure by 15.
If you assume boulders have to be hauled from a stone quarry some 20-30km away (not unrealistic), add another thousand people only to do the transport. And of course, you need someone who works in the quarry. Plus, all those people need to be fed, and protected from robbers / looters.