I did try temporarily turning off the firewall but it didn't work. I also tried the new profile thing but that didn't work for me. I did manage to solve the problems I'd been having. I'll explain what I did, even it was just a peculiar coincidence, it might prove to be a useful option for others having trouble.
I did a "nuclear" version of "turning it off and turning it on again". I switched off every single wifi device in my flat, finishing with the router. I then switched them back on one by one. I obviously started with the router then the mac that was causing all the trouble. After that I turned on my phone which paired to Alfred with no trouble. Then the other mac followed by my iPad. I then successfully paired the iPad to the second mac. I am keeping one remote per device for now, though I doubt that will causes a problem to have both devices act as remotes for both macs. After that the Apple TV and the PS3 went back and there've been no problems since.
By the time I resorted to switching everything off I couldn't get anything to work on AirPlay, so I think some sort of gremlin had got into the wifi set up (perhaps caused by a crash of the Apple TV earlier in the week).