I have never grafted on a plum (and I’m a relative newbie) so take with a grain of salt. But my understanding is that plums are not as easy as pears and not as hard as peaches and that they graft well, so this should work:
I have found it easiest and most successful to do a simple splice graft to a shoot that is vigorous and that is the same diameter as the scion.
I would not prune until I was ready to graft this spring. - The most I might do is cut out that one inward facing big branch that crosses the others. I know I wouldn’t want to graft to that one.
I would pick some of those shoots that are at a good height and facing in a nice direction and graft to those, then prune out the rest of the shoots. It doesn’t matter too much if the shoot is growing upwards initially, because you can weight it down or tie it down later - as long as you haven’t picked one that’s facing in.
“Good height” can vary. I like things a bit higher because I have some wildlife issues, but lower is better for being able to maintain the tree.
I have generally left some big branches on to provide shade (the peaches I’ve done might get damaged bark if they suddenly have no leaves) and because I’ve worried about killing the tree by chopping it all at once. I have no idea if this is a concern for plums - I’m sure someone knows. When I did pears I didn’t worry about this at all.
When multi-grafting you’re supposed to put the less vigorous things at the top and more upright. So you could think about that too -when you’re picking what to prune off.
Also, here is a thread where people were grafting to what I believe is “cherry plum”. You could poke around and see what was successful for them!