Is that normal for newspaper style — to begin a sentence with plus as
an implicit negative?

Effectivement, cette phrase est très ambigüe. Comme cette phrase provient d’un journal, je pense que dans ce cas il est de la responsabilité du journaliste d’éviter une mal compréhension de son article, et non pas au lecteur de le deviner.

Je pense tout de même que dans cette phrase, l’auteur souhaite exprimer l’idée d’augmentation :

• On remarque dans la phrase un pluriel au mot frontières, signifiant qu’il y aurait plusieurs frontières. S’il s’agissait d’une diminution, je pense que plus de frontière aurait été plus juste (zéro est singulier en français).

• D’un point de vue plus littéral, si l’on souhaite exprimer l’idée de diminution, reformuler la phrase plus aucune frontière aurait été (à mon avis) plus naturel même pour le rédacteur : je suppose que c’est ce qu’aurait fait l’auteur.

Cela reste néanmoins à relativiser avec le contexte : Si le titre de l’article est “Doit-on diminuer le contrôle aux frontières européennes ?”, on peut supposer que Plus de frontières entraînerait … signifierait ici moins.

Quoi qu’il en soit, l’auteur aurait pu être plus clair dans ses propos, en utilisant :

Davantage de frontières … (augmentation)

Plus aucune frontière … (diminution)

Le Petit Robert gives a few examples of plus at the beginning of clauses where they definitely mean no more.

Let’s start with Jean-Paul Sartre:

«Paris était mort, plus d’autos, plus de passants»

Here, occurences of plus are preceded by the hint on how to understand them (since Paris is dead, we would expect the disappearance and not the increasing of cars and people), which makes them a little more digestible than the original example provided (Plus de frontières).

Now, a «Plus de guerres, Plus de sang!» that could be quite ambiguous (and disturbing) pulled out of its context. Inspecting the words that come around this worrisome exclamation in Baudelaire’s Le calumet de la paix proves comforting:

Effacez dans les flots vos couleurs meurtrières.
Les roseaux sont nombreux et le roc est épais;
Chacun en peut tirer sa pipe. Plus de guerres,
Plus de sang! Désormais vivez comme des frères,
Et tous, unis, fumez le Calumet de Paix!»

So when using plus without ne, at the beginning of clauses, one should be cautious and look closely for possible misinterpretations. Context should provide the answer, and as shown by the contrast of the original example and the citation from Sartre here above, it might be wiser to provide it before than after…

…unless, as Mistalis mentioned, you decide to adjoin words like aucun or le moindre immediately after plus, in which case you quickly make the negative statement clear:

• Plus aucune frontière → note the singular, while «Plus de frontières» was/would be plural.
• Plus le moindre bruit.
• Plus une seule miette.

However, clarifying a positive statement starting with plus is not that easy. Mistalis’ way of doing it (replacing plus by davantage de) is also the only formal option I could think of, but it is a workaround that somewhat seems to deny the possibility of using this type of plus. This is in contradiction with the actual usage, and arguably a statement that the written form is a purer medium than the spoken form, since speech ignore this specific ambiguity (see the Speak out loud section).

Finally, though, here are a few cases where the sense of such a plus would quite clearly and unambiguously be negative, without any further explanation or context:

• Plus d’hésitations à avoir! ou Plus d’hésitation à avoir !
• Plus un mot!
• Plus de doutes possibles! ou Plus de doute possible !

As suggested by Mistalis, I included the singular versions of the first and third examples. I also decided to stick to my originals, though, since the plural is attested in many respectable works, like Baudelaire cited above, or le Dictionnaire de l’Académie (8ème édition): «Plus de larmes, plus de soupirs, plus de chagrin».

Speak out loud and remove any doubt

As Stéphane Gimenez cleverly mentioned in a comment under the original post, the oral version would be clear and require no context for the audience to understand which one is meant:

Plus no more = /ply/ → Plus de frontières /ply.d(ə).fʁɔ̃.tjɛʁ/ (No more borders)
Plus more = /plys/ → Plus de frontières /plys.də.fʁɔ̃.tjɛʁ/ (More borders)

And like he also said, this is a rare case where speech would gain clarity over writing in French. An English approximation could be read, past and present forms, but their meanings are not nearly as opposed as these two pluses.

Some writers, unafraid of breaking the rules, will spell plusse to emphasize the pronunciation and make sure the word is understood as more of. This spelling is also common in some online forums, though it will usually come along with several other hints of a very relaxed attitude toward grammar, spelling and clarity. While one might genuinely try to make a point of justifying its value, extreme caution is highly recommended concerning its use in almost every situation but the most informal, at least until it gains some acceptance (if it ever does). Here is an excerpt of the immortal Sagouine, by Antonine Maillet, using this casual spelling:

Pis vient un temps que tu jongles plusse parce que t’es pus aussi jeune que t’avais accoutume. Ça vient avec les années, ça la jonglerie. C’est peut-être parce que quand c’est que tu viellzis, t’as plusse de temps pour jongler… C’est malaisé à saouère.

Though it illustrates a different use of plus(se), it does it so wonderfully that I could not pass on it. Sorry to all those who couldn’t make sense of this very strong Acadian parlure.

And finally, this question goes through the various pronunciations of plus very thoroughly and beautifully.