Hard to respond not knowing about your general level of conditioning and other details. A few thoughts:
* Pavement wasn't designed with feet in mind. Feet weren't designed with pavement in mind. Do your best to find other more forgiving, or at least more variable, surfaces to walk on.
* 'Full pack weight' can mean 10 lbs. or 50, depending on the website! You may want to add pack weight, miles, and intensity, more gradually. Be sure to incorporate plenty of rest to the routine, and don't be afraid to vary it up with biking, jogging, etc. If you aren't already incorporating UL practices in your hiking, you've already discovered one of the best reasons for doing so!
*If pavement is a must...Many different opinions on this, but from a post by Andrew Skurka: "If you are going to be on hard surfaces day-in-day-out, then I'd recommend either a GoLite shoe...or a lightweight trail runner or 'day hiker' with a forefoot plate. Basically, your goal is to stay away from an EVA mid-sole, which is collapse-prone and after that your 'cushioning' is gone. A growing number of people seem to be fans of minimalist shoes with no cushion, but I think this is impractical for hard-packed, cobblestone-laden trails while wearing a backpack -- your feet get eaten and eventually bruised."
*Adding extra insoles, arch support etc. (see Roger Caffin's convincing theory that arch support is a cynical marketing ploy by Nike) can make it more difficult to find the underlying issues of discomfort, and perhaps make them worse. Best to address other issues before taking this step, which leads to the next point...
* Your issues may have little to do with either arches or cushioning. Your feet are only part of a process which includes not only your overall physical state and gear choices, but also your training strategy. What are you training for- general fitness, a through hike, weekend family trips? Are extended training hikes with a loaded pack a safe, efficient, and effective use of time? Suffice to say that many approaches emphasizing general strength and conditioning will translate to hiking. My somewhat informed but still very much amateur opinion: regular sessions of long duration/ high repetition movement (especially under load) such as hiking with a pack will over time lead to adaptation, diminishing results, and eventually injury without a plan that incorporates 1)forms of mobility and, for lack of a better word, 2) stretching.
For an example of mobility movement, see http://www.youtube.com/watch?v=pFugm34H_IQ&feature=related.
For an example of "stretching" in the form of prasara yoga, see http://www.youtube.com/watch?v=LLB-yAYHs7A.
I am not affiliated with Scott Sonnon or any CST (Circular Strength Training) entity, but have used CST products with great success. Though much of the marketing is absurd, I appreciate the health first approach of CST. The content itself is very high quality, and will resonate with those who have had experience in yoga, tai chi, martial arts, and so on. Mobility work in particular can be easily incorporated into hiking and backpacking. I believe it goes a long way towards avoiding/reducing injury and increasing comfort, particularly on extended trips.
Whatever route you go, perhaps this is an opportunity to become more disciplined and deliberate in your physical practice. Be aware that many proponents of different products out there may be the result of the survivor effect- it worked for them, but this does not mean that it will work for you, because proponents are typically by definition the ones it worked for. People who see "results" may have incurred damage that will only reveal itself over time, and they may have succeeded despite rather than because of their training.
Hope this helps.