If it's just marked as USA for manufacture then that's not relevant.
If it's to US standards but not to European or older British HSE standards then it's not legal to fill in the U.K.
It needs to have the Pi symbol on it, and to be in date to be legal to fill in the U.K.
It's likely to be that they meant that they do not have a paintball fill adaptor.
APS Marine are the only dive centre in Salisbury. To get a fill you will need to get to a paintball site, the nearest being at Landfor on the way to Southampton. Paintball sites will give free fills when playing
I used APS Marine to arrange hydro test once. The first guy I asked was very happy to arrange it for a paintball cylinder (but said it would be some time as they would send dive bottles in batches, no problem)
When I returned to collect it he was even happier as while it was sat in the shop many divers were commenting on it as a good size for a miniature pony dive cylinder, and I had offers to buy it. (I didn't want to, but he possibly gained some sales on new paintball cylinders)
They had also filled my cylinder, and it was USA manufactured but to TPED European approved standard
As I had got a good test price a little later I returned to ask for a price on testing a batch of aluminium cylinders. This time i spoke to a different guy who was unfriendly to paintball and given a ridiculous price to get rid of me
This may be some ignorance about your cylinder thinking USA manufacture means it is a US only bottle (but cylinder standards should be easily recognised by a dive shop). Or they may be right and it isn't to European standard