In general, 2 trees can be 50ft apart and pollinate each other without any problems. If the type of fruit tree is common in the surrounding neighborhood, the trees can be much further apart than that, because a visiting bee is likely to have some pollen on it from another tree somewhere in the neighborhood. The only time there may be trouble is if the 2 trees are very young and do not produce many blossoms. If they do not attract a sufficient number of bees, the chances of cross-pollination may be too low and the trees would have produced more fruit if they had been planted right next to each other.

Having many plants that attract bees can help compensate for this. As a hypothetical example, if you have 2 young cherry trees that are planted 52ft apart, both of which need a pollinator and neither has many blossoms, the blossoms are more likely to set fruit if there is a mature apple tree in the middle (one which blossoms at the same time as the cherries), because the blossoming apple tree will attract many bees to the surrounding area.

This is just my opinion not based on any hard facts, but in general if you are planting 2 fruit trees and you want lots of fruit within the first 4 years, you should probably plant them within 15-20ft of each other for maximum pollination.

You can also just graft on another beach plum (assuming it was not clonally propagated from the same line) onto the same tree to make it self-fruitful. This may be the best option for you.

In many years when the trees have become larger and more mature, pollination will not be an issue anymore.

The two oldest of them are close to a bunch of beach rose. (Rugosa Rose?) The two smallest are rather tiny. What blooms at the same time as beach plum? And will the problem take care of itself when they get bigger?

Beach plums are not as big as apple or cherry trees. I would try to keep them planted within 30ft of each other. Unless beach plums are common in your area.

You might want to plant them in pairs.

The good news is that beach plums are considered a more wild variety, so from that I would guess that they are excellent pollinators.

I believe some varieties of Beach plum are sold as self-fertile, so if that is the case you would not need a pollinator. But I am assuming that since you posted this thread, the label on your plants said it needed a pollinator ('self-sterile').

Disclaimer: I am not familiar at all with Beach plums, just giving advice based on my knowledge of fruit trees in general. I really have no idea, but I suspect Beach plums may be one of those plants that are partially self-fruitful (meaning they can pollinated themselves, but bear much more fruit if there is another variety around).

The label didn't say, but no fruit so far. The big potted beach plums I have luck with are a bit pricey. Little luck so far with the tiny bare root ones. I had heard they spread, and due to the price I bought one a year and put it in the spots I wanted Beach Plums, hoping they would spread to fill the space.

This is an interesting article:

http://www.nytimes.com/2003/09/03/dining/beach-plums-hard-to-tame-but-growers-don-t-give-up.html