That can sure happen. Charles Petty did a test in 2006 firing the .224 55 grain Hornady V-max with 24 grains of reloader 10X in a 223 bolt rifle, changing only the primers, of which he included many from standard through magnum. His results spanned averages of 3150 to 3300 fps. He would have had to increase the load a full grain to get that velocity difference with his mildest primer (a Federal 205 standard primer; I've forgotten which magnum primer was warmest for him).
The magnum primer's main function to make more gas than a standard primer. This does the initial pressurizing of the case which is necessary to get adequately consistent ignition speed and to prevent powders with significant levels of deterrents coatings from squibbing out. The name "magnum" comes from the fact magnum rifle cases have more space in them to pressurize, but they are also appropriate in non-magnum cases either when the powder charge doesn't fill the case well (making more empty space to pressurize) or when the powder is hard to ignite as a number of older spherical propellants are.
That said, there are also times when magnum primers reduce velocity. This tends to happen in smaller capacity cases for which the primer can start to unseat the bullet and increase the volume before the powder gets fully burning. The .22 Hornet is notoriously sensitive to this. But any gun with a long throat can potentially have it happen.
Larger capacity cases are less sensitive to primer choice. You frequently see tests of .30-06 and other cartridges that normally use large primers done with different standard and magnum primers and for which you see so little velocity difference it is almost statistically insignificant. However, I have seen the adoption of the CCI #34 improve accuracy significantly in the M1 Garand as compared to a Federal 210M. Garand loads are typically poor case fillers in the 80-85% loading density range.
I can only advise that you test primers to see which one produces the lowest velocity standard deviation with your powder as an indication of which one is producing the most consistent ignition. The difference in accuracy in the case of the Garand was almost certainly due to the ignition time, which ads to lock time, becoming more consistent so the direction the muzzle was pointing experienced more identical disturbance from shot to shot.
I will add that the disappearance of the Tula primers has been disappointing as they produced the lowest velocity SD in the Garand of any primer I've ever used. I am still sitting on a full slip each of their small and large NATO primers, but am starting to load them and fear they will not return any time soon. If the Tula plant every figures out how to eliminate the lip burrs, they will probably be the best primers made anywhere. You can fault the Russians for many things, but not for their enthusiasm and dedication to target shooting competition and the materials needed for it.