Is Waterloo as important a station to keep changes to a minimum as it was 15 or more years ago, now that the Eurostars run from St Pancras?
It's still the terminus station for a fair chunk of the south coast.
Though the lack of a direct service between kings cross and waterloo is mitigated for long distance journeys by the availaibility of crosscountry trains and for more local jouneys by the availability of thameslink. It's a shame the rail planners don't understand that some "tube" fixed links require a change between two tube lines causing them to produce iteneries that involve unnecessary changes.
Which is easier for Paddington out of Kings Cross or Euston?
For paddington from Either Kings cross or Euston you would use the subsurface underground lines.
At Kings cross/St pancras the subsurface station is an integrated part of the station complex, the walk is annoyingly long but at least it's undercover and on smooth floors with lifts available if you need them (though the paddington end still appears to be limited step free access wise).
At Euston you have to leave the main station and find your way to the seperate "Euston Square" station that serves the subsurface lines. Actually finding the location of said entrances from online information seems to be non-trivial, I've no idea how easy/difficult it is when you are actually on the ground.