かのよう（だ） translates as ‘(seems) as if...’ or ‘(seems) as if perhaps...’ while (depending on the sentence) ようだ can be less conjectural.
…なにもなかったかのように… ‘as if nothing had happened’
…なにもなかったように… ‘it looked like nothing had happened’
However, in counter-factual statements, ようだ can lend this meaning all by itself. Often (as in the sentence of the question) まるで is added for emphasis, and まるで…ようだ and …かのようだ would seem equally conjectural.  
木村さんはまるで酒を飲んだようだ Mr. Kimuro looks as if he had just drunk sake. 
That means that the sentence 「４月になって雪が降るなんて、まるで冬が戻って来たかのようです。」 (considering that April is well past the winter season) taken as a whole would not really change its meaning when you replace かのようです with simply ようです (it would be different in only the fragment 戻って来たようです/戻って来たかのようです, depending on the context). Removing まるで as well might make the sentence less emphatic, but since it is still an ‘as if’ scenario the meaning would basically remain. A real difference would only appear in sentences that are more statement of fact.
As for the second question (are there restrictions regarding active use of かのようだ instead of ようだ), not being a native speaker I wouldn't know how to answer that for sure.  seems to be from a native speaker and he or she does seem to be unable to answer this very same question right away (see at the bottom of the page) but does suggest that かのようだ is much less common in set phrases like 水を打ったよう ("水を打ったかのよう" 19,400 results versus "水を打ったよう" 4,590,000 results in Google).
- Samual E. Martin A reference grammar of Japanese (p. 929).
- Makino and Tsutsui A Dictionary of basic Japanese grammar (p. 549)/
- It's not simply the か in かのようだ, you can not leave the の in between verb+ようだ either.