I fly quite often with CSA Czech Airlines (definitely not "Czech Air"!), who usually offer very good service so I'm willing to bet they would gladly help you connect to another of their flights. It is 100% certain that your luggage will be waiting for you at the final destination of your choice. Flying with separate tickets, however, might necessitate a very quick airside check-in at PRG- I sometimes have to do that even when flying on a single ticket if the connection is a bit long or the outstation handling agent not well-equipped/trained enough to issue onward boarding passes.
If I were you I would choose Kraków as opposed to BUD or Berlin....IMHO it's far more picturesque and characterful than the other two, and prices will most likely be lower too. The only downside is the ATR42 that will take you there from PRG, which is cramped and a bit noisy. But by flying it you 'll get to see one of the world's very few Business class cabins (though the seats are the same, of course) at the rear of an aircraft!
Minimum connection time in Prague is 35 minutes which can be done very easily due to the clever layout of the terminal and the fact that security (apart from passport control, which of course has nothing to do with transiting pax) only happens at the departing gate (consequently no chance of you missing the plane by a security queue). If you are not familiar with the airport and run the risk of needing a boarding pass at PRG, leave an extra 10 minutes.
If you do fly to BUD remember that some flights (OK 3XXX or 4XXX) are operated by Malév so you might have problems crediting your miles outside OK+. Also remember to check the schedules if you have an irrational fear/dislike of RJs and turboprops, I think all MA flights are on RJs, while OK-operated flights are split between the ATR72 (far more spacious config than the OK ATR42) and B73X.