From my understanding of the root of the term, I think it is technically correct. Typically, the idiom is "comes with," for example:
The number seven burger comes with fries.
I think the journalist is alluding to the common quote "with great power comes great responsibility," which is often attributed to Voltaire, FDR, Stan Lee himself (in Spider-man form Amazing Fantasy #15, 1962). http://en.wikiquote.org/wiki/List_of_misquotations
In this case, the idiom can be simplified to avoid a preposition at the beginning of the sentence or phrase, in your case "such stature comes with increased responsibilities," but I think both are grammatically acceptable. I think the role of prepositions at the beginning and end of sentence and phrases has been decried by pedantic grammarian grade-school teachers, but ultimately I think it's a preference. The literature shows acceptable usage of both.
As far as the subject/verb agreement, I think that comes refers back to stature, which is singular, and as such should be acceptable.
EDIT:
This question was edited after my initial answer, so I'll edit the answer as well.
In my example, I meant to explain that when you re-organize the words, the organization becomes more clear. What is coming with what? To simplify your sentence, would it make more sense to say that "Stature comes with increased responsibilities" or "Responsibilities come with increased stature." Logic tells me that the first fits the intent, as the responsibility is not causing the increase in stature: rather the implication is that stature will elicit increased responsibilities. In this case, it becomes more clear to me that the subject is in fact "stature," and "with responsibilities" acts as a prepositional phrase to modify the verb "comes."