From the Man in Seat 61-
Anyone from any country can order tickets from reliable Polish agency www.polrail.com and pay extra for tickets to be sent to you, although this will cost a lot more than buying a cheap advance-purchase ticket from Hungarian Railways direct. For cheapness, consider option 2 below.
Option 2, consider catching the 18:40 EuroCity train from Budapest Keleti to Vienna Hbf, then using using the 23:10 Vienna-Krakow sleeper train instead, see times & fares here - the Vienna-Krakow(-Warsaw) sleeper arrives at Krakow coupled to the Budapest-Krakow(-Warsaw), they are two portions of the same train. By all means book an earlier train from Budapest and have dinner in Vienna! You can easily buy a cheap Sparschiene fare in a couchette or sleeper from Vienna to Krakow at the www.thetrainline.com or at the Austrian Railways website www.oebb.at with tickets that can be printed out.
Tip: The sleeper arrives in Krakow at an early hour. Exit the station through the shopping centre and you'll find the Hotel Puro Stare Miasto on the other side of the road and to the right. They'll let you join their excellent breakfast buffet from 7am for around €16.