However, the Kings this season could make that kind of deal because of the larger salaries of both Shumpert and Randolph, and the capspace they have.
For me, the issue is not what we can offer, but what we can get in return.
While we don't have a first round pick this year, we have a huge number of young prospects (and even some vets) on very team friendly contracts, a plethora of second round picks, multiple expirings with large values. And yes, we are the only team with a sizeable cap space to provide immediate relief and lot of flexibility. So, short of a team looking for a star, first round pick, we are an ideal trade partner.
The issue is what we get in return. Given our huge number of young assets, many of whom we can reasonably hope for as potential stars in near future, we are not really looking for young, marginal talents. They'll take up roster spot, without seeing much time, and we already have a lot of them. No team is giving us their star for what we can offer, or even a potential young stud.
We may be able to snag a decent ranked first round pick for Willie (in a multi player trade), but I don't know how I feel about that. If he's not part of our future, then sure, get the best we can get for him. First round picks are valuable, and can be used to make other trades. However, if we keep the pick, one in the teens (I doubt we get anything higher), is unlikely to help us much. Sure, the kid we draft will be on a rookie contract for 4 years, while Willie will need to get paid after this year. However, unless Willie really blows this year (in which case, we shouldn't trade him anyway), I'm not sure we'll need to overpay for him that much.
Plus, the draft is always dicey. Willie himself was the 6th pick. If all we are doing is turning him into a pick in the teens (in what some folks are projecting to be a weak draft), that's pretty poor return. We may get ourselves a stud or a very nice player there too, but chances are not too bright.
The only worthwhile trades I can think of are either with the Wizards, or Wolves. Wizards might fancy themselves as the 4th/5th best team in the East (and if Kawhi bolts next year, they can legitimately think of contending for ECF. I think Boston and Philly will both be better than them, and maybe even Pacers, but an injury or lucky bounce can swing a close series), but they are paying a pretty penny for Otto. With Willie, they shore up their frontline for the future. We get the 3 we need.
As for Wolves, there have been some rumblings from there about Wiggins and his role, Butler, and even Towns. They are likely to miss the playoffs in the revamped West, and might want to cut ties with a player who hasn't lived up to his contract. While overpaid, he might fit with us, as he fills the position of need, is only 23, and we will need to pay someone anyway to even meet the floor.
As you said though, it takes two to tango.