I cut into my drywall to locate the mechanical runs in the wall between the kitchen and dining room. The sketch below shows the relative position of the proposed opening in the wall with respect to the existing plumbing and HVAC runs (click the pictures for an enlarged view).
Moving the duct over a couple of studs will be simple enough from the basement. To reconnect the HVAC to the run in the ceiling joists, the duct will need to go in through the ceiling because of the addition of the new header at the existing duct. That duct will be run be on the kitchen side of the wall and can be covered by a soffit.
The existing drain pipe is located right next to where the new sink will be added. I think that to move the water pipes, they may need to be run into the upstairs wall, then reconnected by opening the drywall upstairs. On the bright side, water is available right where it is needed.
I had a contractor look at the project today. He says the project is doable and will provide me a quote for the work.