come complete withについて

おそらく違和感の原因は、
come with を一つの動詞表現（＝付属する）として捉えているところから来ているのかな？という気がします。

仮に、その見方を前提にすると、
「付属する」という動作をどう修飾するか、という発想になるため、
動詞を修飾する副詞 completely なら自然に思えるのかもしれません。

一方で、complete（形容詞）が come と with の間に入る形は、
動詞句の途中に状態語が割り込んでいるように見え、そこに違和感を感じるのかもしれません。

ただ、英語では、必ずしも come with が一まとまりの動作として捉えられているわけではなく、
come complete（完備した状態にある） という状態表現が先にあり、with ～ はその状態の内容を補足していると考えられることが多いです。

そのため、completely のような「動作のしかた」を表す副詞を置く対象がなく、
結果として complete が使われていると理解するのがスムーズではないでしょうか。