I'd say it is possible. Reading some of the details around 1st Company marines, while most have hundreds of years of experience, a singular act of insane heroism is also qualifies a marine. If their battle brothers believe that they have what it takes, that is all that is required. Just usually those centuries of service are what counts as appropriate evidence.
Which brings us to the Primaris Marines - they are good. Very good. Loyalist Primarch gene seeds and Custodes creation methods are combined to make them bigger and better, and this is reflected in the tabletop stats. Being a project of Roboute Guilliman should make the Ultramarines the most open to accepting the Primaris Marines, so even the excuse of tradition is flimsy. In short, I don't think it would take long for a Primaris Marine to go above and beyond and prove themselves worthy of 1st Company.
Additionally: The Rubicon Primaris is a process which turns a regular Space Marine into a Primaris Marine. It is painful, lengthy, with a high failure rate (the first subject in fact died on the table and was revived), but it worked. Marneus Calgar rose a Primaris. I'd say it is natural that the strongest, toughest and most valiant Marines of 1st Company would be prime stock for upgrading. So those Primaris Marines in 1st Company might actually be true veterans as well!