Well, I think I have a solution - this is my first post so if it turns out I'm wrong or this is well-known, my apologies

All I had to do to ensure the correct tempo saving with every "ALL" slot was to re-write one of the program settings before saving - making sure it's a BPM-locked program, saved while on the correct tempo (I was using Loop-1 but I'm assuming it works with any BPM-locked program).
So for example, with the KP3 set to the BPM I want, I load up my four samples and do all my settings and whatnot, then before saving I select Loop-1 and Write it to one of the 1-8 program presets. Then, with that program preset active (not sure if that step is important) I do a Save ALL. Now every time I load that slot, it loads it at the appropriate tempo, regardless of what the BPM is set to before I load.
Hope that makes sense, and hope it helps people out
