Sachverhalt:
Sachverhalt:
A. Der 1963 geborene X._ ist Staatsbürger von Serbien und Montenegro. Er wuchs in seiner Heimat auf. Nachdem er sich bereits seit 1985 als Saisonnier in der Schweiz aufgehalten hatte, reiste er 1989 offiziell ein. Im gleichen Jahr heiratete er eine Landsfrau. Sie haben vier Kinder, die in den Jahren 1984, 1990, 1991 und 1994 geboren wurden. X._ arbeitete in der Schweiz nur sporadisch als ungelernte Hilfskraft. Die Familie bezog Sozialhilfe. 1997 lösten die Eheleute den gemeinsamen Haushalt auf. Der Kontakt zwischen X._ und den Kindern brach in der Folge während mehrerer Jahre ab. Am 1. März 2002 wurde die Ehe durch Scheidung aufgelöst.
Nach einer ersten Verurteilung im Jahre 1994 wegen Beihilfe zu illegaler Einreise wurde X._ 1996 wegen versuchter Vergewaltigung und Pfändungsbetrug zu 16 Monaten Gefängnis und fünf Jahren Landesverweisung mit bedingtem Vollzug verurteilt. Im Zusammenhang mit diesem Strafverfahren wurden die Wegweisung und eine Einreisesperre bis zum 7. April 2003 verfügt. X._ wurde in der Folge ausgeschafft, ein erstes Mal am 10. April 1997 und, nachdem er trotz Einreisesperre wieder eingereist war, ein zweites Mal am 9. April 1998. Bereits am 28. November 1998 reiste er wieder ein und stellte ein Asylgesuch. Dieses wurde am 8. Mai 2002 in letzter Instanz abgewiesen. Unter Hinweis auf die Beziehungen zu seinen Kindern hatte er bereits am 25. April 2002 ein Gesuch um eine Aufenthaltsbewilligung gestellt. Dieses Verfahren soll noch hängig sein.
Nach einer ersten Verurteilung im Jahre 1994 wegen Beihilfe zu illegaler Einreise wurde X._ 1996 wegen versuchter Vergewaltigung und Pfändungsbetrug zu 16 Monaten Gefängnis und fünf Jahren Landesverweisung mit bedingtem Vollzug verurteilt. Im Zusammenhang mit diesem Strafverfahren wurden die Wegweisung und eine Einreisesperre bis zum 7. April 2003 verfügt. X._ wurde in der Folge ausgeschafft, ein erstes Mal am 10. April 1997 und, nachdem er trotz Einreisesperre wieder eingereist war, ein zweites Mal am 9. April 1998. Bereits am 28. November 1998 reiste er wieder ein und stellte ein Asylgesuch. Dieses wurde am 8. Mai 2002 in letzter Instanz abgewiesen. Unter Hinweis auf die Beziehungen zu seinen Kindern hatte er bereits am 25. April 2002 ein Gesuch um eine Aufenthaltsbewilligung gestellt. Dieses Verfahren soll noch hängig sein.
B. Das Obergericht des Kantons Bern verurteilte X._ am 11. Juli 2002 wegen mehrfacher sexueller Handlungen mit einem Kind, begangen im Sommer 2001, zu 12 Monaten Gefängnis, unter Anrechnung der Untersuchungshaft, und zu fünf Jahren Landesverweisung. Der bedingte Vollzug wurde für die Haupt- und die Nebenstrafe verweigert. Eine dagegen eingereichte staatsrechtliche Beschwerde wurde durch das Bundesgericht abgewiesen (Urteil 1P.480/2002 vom 30. Oktober 2002).
B. Das Obergericht des Kantons Bern verurteilte X._ am 11. Juli 2002 wegen mehrfacher sexueller Handlungen mit einem Kind, begangen im Sommer 2001, zu 12 Monaten Gefängnis, unter Anrechnung der Untersuchungshaft, und zu fünf Jahren Landesverweisung. Der bedingte Vollzug wurde für die Haupt- und die Nebenstrafe verweigert. Eine dagegen eingereichte staatsrechtliche Beschwerde wurde durch das Bundesgericht abgewiesen (Urteil 1P.480/2002 vom 30. Oktober 2002).
C. Am 29. November 2002 heiratete X._ nach einer zweijährigen Beziehung die italienische Staatsangehörige A._, die in der Schweiz eine Niederlassungsbewilligung besitzt. Zu den Kindern aus erster Ehe pflegt er wieder vereinzelte Kontakte. In der Schweiz leben überdies seine Eltern und Geschwister, mit Ausnahme einer Schwester, die sich im Kosovo aufhält.
C. Am 29. November 2002 heiratete X._ nach einer zweijährigen Beziehung die italienische Staatsangehörige A._, die in der Schweiz eine Niederlassungsbewilligung besitzt. Zu den Kindern aus erster Ehe pflegt er wieder vereinzelte Kontakte. In der Schweiz leben überdies seine Eltern und Geschwister, mit Ausnahme einer Schwester, die sich im Kosovo aufhält.
D. X._ trat den Vollzug des noch nicht verbüssten Restes der am 11. Juli 2002 ausgesprochenen Strafe am 2. März 2003 an.
Mit Verfügung vom 14. März 2003 bewilligte die Abteilung für Straf- und Massnahmenvollzug des Kantons Bern die bedingte Entlassung aus dem Strafvollzug auf den 3. April 2003, unter Auferlegung einer Probezeit von zwei Jahren. Gleichzeitig lehnte sie es ab, den Vollzug der Landesverweisung probeweise aufzuschieben.
Die kantonale Polizei- und Militärdirektion wies eine dagegen eingereichte Beschwerde am 8. Juli 2003 ab.
X._ focht die Verweigerung des probeweisen Aufschubes der Landesverweisung beim Verwaltungsgericht des Kantons Bern an. Dieses wies die Beschwerde am 8. März 2004 ab.
X._ focht die Verweigerung des probeweisen Aufschubes der Landesverweisung beim Verwaltungsgericht des Kantons Bern an. Dieses wies die Beschwerde am 8. März 2004 ab.
E. Gegen den Entscheid des Verwaltungsgerichts führt X._ mit Eingabe vom 8. April 2004 fristgerecht Verwaltungsgerichtsbeschwerde beim Bundesgericht. Er beantragt, es sei die mit Urteil des Obergerichts des Kantons Bern vom 11. Juli 2002 ausgesprochene Landesverweisung probeweise aufzuschieben. Der Beschwerde sei die aufschiebende Wirkung zu erteilen.
Die Vorinstanz beantragt in ihrer Vernehmlassung vom 19. April 2004, die Beschwerde sei abzuweisen, soweit darauf einzutreten ist.

Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. An die Feststellung des Sachverhalts im angefochtenen Entscheid ist das Bundesgericht im vorliegenden Verfahren gebunden, wenn das Verwaltungsgericht diesen nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt hat (Art. 105 Abs. 2 OG). Dass eine dieser Voraussetzungen erfüllt wäre, ist der Beschwerde trotz des Hinweises auf Art. 105 Abs. 2 OG nicht zu entnehmen. Auf die Beschwerde ist folglich insoweit nicht einzutreten, als darin vom Sachverhalt des angefochtenen Entscheids abgewichen wird.
1. An die Feststellung des Sachverhalts im angefochtenen Entscheid ist das Bundesgericht im vorliegenden Verfahren gebunden, wenn das Verwaltungsgericht diesen nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt hat (Art. 105 Abs. 2 OG). Dass eine dieser Voraussetzungen erfüllt wäre, ist der Beschwerde trotz des Hinweises auf Art. 105 Abs. 2 OG nicht zu entnehmen. Auf die Beschwerde ist folglich insoweit nicht einzutreten, als darin vom Sachverhalt des angefochtenen Entscheids abgewichen wird.
2. Der Beschwerdeführer rügt eine Verletzung von <ref-law>.
2.1 Gemäss <ref-law> kann der Richter einen Ausländer, der zu Zuchthaus oder Gefängnis verurteilt wird, für drei bis 15 Jahre aus dem Gebiet der Schweiz verweisen. Wird der zu einer unbedingten Freiheitsstrafe Verurteilte bedingt aus dem Strafvollzug entlassen, so entscheidet die zuständige Behörde, ob und unter welchen Bedingungen der Vollzug der seinerzeit ausgesprochenen unbedingten Landesverweisung nachträglich doch noch probeweise aufgeschoben werden soll (<ref-law>).
Der Entscheid über den probeweisen Aufschub der Landesverweisung steht mit dem Entscheid über die bedingte Entlassung aus dem Strafvollzug in engem Zusammenhang. Bei beiden Entscheiden ist dem Ziel, den Verurteilten zu resozialisieren, Rechnung zu tragen. Massgebend beim Entscheid über den probeweisen Aufschub der Landesverweisung ist, ob in der Schweiz oder im Ausland die besseren Chancen für die Resozialisierung des bedingt aus dem Strafvollzug Entlassenen bestehen (<ref-ruling> E. 3a S. 59; <ref-ruling> E. 2c S. 110). Der Gesichtspunkt der öffentlichen Sicherheit ist nur bei der Anordnung und Bemessung der Landesverweisung, im Zusammenhang mit der Frage nach deren probeweisem Aufschub jedoch nicht mehr zu berücksichtigen (<ref-ruling> E. 2e S. 287).
Die Resozialisierungschancen sind nach den persönlichen Verhältnissen des Entlassenen, seinen Beziehungen zur Schweiz und zum Ausland, den Familienverhältnissen und den Arbeitsmöglichkeiten zu beurteilen. Dabei ist auf seine wahrscheinliche künftige Lebensgestaltung abzustellen. Die zuständige Behörde urteilt in dieser Frage weitgehend nach ihrem Ermessen, in welches das Bundesgericht nur mit Zurückhaltung eingreift (Art. 104 lit. a OG). Bei dessen Ausübung muss sie sich allerdings auf sachlich haltbare Gründe stützen. Insbesondere darf der Entscheid, ob der Vollzug der Landesverweisung bedingt aufzuschieben sei, nicht auf Überlegungen gestützt werden, die mit Sinn und Zweck der bedingten Entlassung unvereinbar sind. Das Bundesgericht hebt den angefochtenen Entscheid auf, wenn die Vorinstanz nicht von rechtlich massgebenden Gesichtspunkten ausgegangen ist oder diese in Überschreitung oder Missbrauch ihres Ermessens unrichtig gewichtet hat (<ref-ruling> E. 2a S. 285).
2.2 Die Vorinstanz hat sich zur Frage der Resozialisierungsaussichten eingehend und überzeugend geäussert, worauf hier verwiesen werden kann (vgl. angefochtener Entscheid S. 6 - 15 E. 4 und 5). Der Beschwerdeführer sei den Beweis dafür, dass er sich integrieren wolle und dazu überhaupt fähig sei, schuldig geblieben. Insbesondere habe er sich nicht bemüht, im Erwerbsleben Fuss zu fassen. Unter diesen Umständen stünden seine Chancen für eine Sozialisierung in der Schweiz schlecht. Heute wäre es für ihn voraussichtlich sehr schwierig, als ungelernte Arbeitskraft mit wenig Erfahrung und ohne Leistungsausweis eine berufliche Existenz in der Schweiz aufzubauen, zumal seine Vorstrafen bei der Arbeitssuche zusätzlich hinderlich sein dürften. Angesichts seines bisherigen Verhaltens sei auch nicht anzunehmen, dass der Umstand, dass Angehörige in der Schweiz leben, eine Integration fördern könnte. So hätten die Kinder 1998 unter Erziehungsbeistandschaft gestellt und fremdplatziert werden müssen, weil der Beschwerdeführer seinen Pflichten als Vater nicht nachgekommen sei. Auch heute finde der Kontakt zu den Kindern nur in einem sehr lockeren Rahmen statt, weshalb nicht ersichtlich sei, inwiefern die Kinder zu einer Integration des Beschwerdeführers in der Schweiz beitragen könnten. Zwar vermittle eine gelebte Ehe nach der allgemeinen Erfahrung Stabilität. Aber für den vorliegenden Fall sei zu berücksichtigen, dass die heutige Ehefrau bereits die Freundin des Beschwerdeführers gewesen sei, als dieser sich im Sommer 2001 der sexuellen Handlungen mit einem 15 Jahre alten Mädchen schuldig gemacht habe. Dass die neue Ehe einen Resozialisierungseffekt haben könnte, sei vor diesem Hintergrund zweifelhaft. Schliesslich sei davon auszugehen, dass auch die Eltern und Geschwister keinen entscheidenden Einfluss auf die Lebensgestaltung des heute 40 Jahre alten Beschwerdeführers haben dürften, zumal dies ja auch bisher nicht der Fall gewesen sei. Demgegenüber sei grundsätzlich davon auszugehen, dass der Beschwerdeführer in seiner Heimat, wo er nicht vorbestraft sei und eine Zeit lang in einer Fabrik gearbeitet habe, Arbeit finden könne. Die Resozialisierungschancen seien dort folglich jedenfalls nicht schlechter als in der Schweiz.
Diesen Ausführungen ist, soweit sie nicht für das vorliegende Verfahren verbindlich sind, beizupflichten. Die Beschwerde ist in diesem Punkt als offensichtlich unbegründet abzuweisen.
Diesen Ausführungen ist, soweit sie nicht für das vorliegende Verfahren verbindlich sind, beizupflichten. Die Beschwerde ist in diesem Punkt als offensichtlich unbegründet abzuweisen.
3. Der Beschwerdeführer macht sodann geltend, der angefochtene Entscheid verletze das in Art. 8 EMRK garantierte Recht auf Achtung des Familienlebens.
3.1 Art. 8 Ziff. 1 EMRK - und seit dem 1. Januar 2000 auch ausdrücklich <ref-law> - gewährleisten das Recht auf Achtung des Privat- und Familienlebens. Darauf kann sich der Ausländer berufen, der eine familiäre Beziehung oder nahe Verwandte mit einem gefestigten Anwesenheitsrecht in der Schweiz hat. Wird ihm in einem solchen Fall die Anwesenheit in der Schweiz untersagt, kann dies Art. 8 EMRK verletzen (<ref-ruling> E. 2a S. 427; <ref-ruling> E. 1e S. 5). Ein Eingriff in das Recht ist jedoch zulässig, wenn er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ruhe und Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung und zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesundheit und Moral sowie der Rechte und Freiheiten anderer notwendig ist. Die EMRK verlangt also eine Abwägung der sich gegenüberstehenden privaten und öffentlichen Interessen, wobei die öffentlichen in dem Sinne überwiegen müssen, dass sich der Eingriff als notwendig erweist. Dabei ist im vorliegenden Fall insbesondere wesentlich, in welchem Masse sich der Beschwerdeführer strafbar gemacht hat. Nebst den übrigen persönlichen und familiären Verhältnissen ist der Schwere des strafbaren Verhaltens und allenfalls den Umständen des Eheschlusses Rechnung zu tragen. Sodann ist bei der Frage der Interessenabwägung zu fragen, ob der Ehefrau zugemutet werden kann, dem Beschwerdeführer ins Ausland zu folgen. Die Frage der Zumutbarkeit bewertet sich nicht nach den persönlichen Wünschen der Betroffenen, sondern ist unter Berücksichtigung ihrer persönlichen Verhältnisse und aller Umstände objektiv zu beurteilen (BGE <ref-ruling> E. 2 S. 6; <ref-ruling> E. 3a und b S. 6).
Nach der Praxis der Strassburger Organe ist die Ausweisung bei schweren Straftaten auch zulässig, wenn ein rechtmässig begründetes, intaktes Familienleben besteht. Die in Frage stehenden Straftaten müssen allerdings eine gewisse Schwere aufweisen, um eine Familientrennung verhältnismässig erscheinen zu lassen. Das Interesse der Öffentlichkeit an der Ausweisung muss stärker wiegen als etwa die Schwierigkeiten der betroffenen Person und ihrer Angehörigen, sich im Heimatstaat zu integrieren (vgl. Frowein/Peukert, Europäische Menschenrechtskonvention, Kommentar, 2. Auflage, 1996, Art. 8 N. 24; Wildhaber/Breitenmoser, Internationaler Kommentar zur EMRK, 1992, Art. 8 N. 450; René Ernst, Die Landesverweisung gemäss Artikel 55 des Strafgesetzbuches, Diss. Basel 1998, S. 100).
3.2 Die Vereinbarkeit einer Landesverweisung mit Art. 8 EMRK ist bereits bei deren Anordnung zu prüfen. Im Rahmen des vorliegenden Verfahrens ist auf die Frage nur mehr soweit einzugehen, als sich seit der Anordnung der Landesverweisung durch das Obergericht neue Tatsachen ergeben haben.
Neu in diesem Sinn ist der Umstand, dass sich der Beschwerdeführer mit einer in der Schweiz niedergelassenen Italienerin verheiratet hat. Er begründet seine Rüge denn auch ausschliesslich mit der neu eingegangenen Ehe.
3.3 Wie die Vorinstanz festgestellt hat, ist im vorliegenden Fall entscheidend, dass der Beschwerdeführer und seine neue Ehefrau die Ehe erst nach dem Urteil des Obergerichts geschlossen haben, als die unbedingte Landesverweisung rechtskräftig war. Die Ehefrau habe es im Zeitpunkt des Eheschlusses in Kauf genommen, dass sie ihre Ehe unter Umständen im Ausland leben müsse (angefochtener Entscheid S. 13). Diese tatsächliche Feststellung der Vorinstanz ist für das Bundesgericht im vorliegenden Verfahren verbindlich, da der Beschwerdeführer nicht dartut, dass und inwieweit sie offensichtlich unrichtig sein könnte. Auf seine allgemein gehaltene Behauptung, der "Mechanismus" der Landesverweisung sei für einen Laien "nicht ohne weiteres durchschaubar" (Beschwerde S. 7), ist nicht einzutreten. Unter diesen Umständen ist es nicht von ausschlaggebender Bedeutung, dass die Ehefrau gewisse Schwierigkeiten haben könnte, dem Beschwerdeführer in den Kosovo zu folgen (Urteil 2A.549/2002 vom 12. Februar 2003 E. 3.4 mit Hinweis auf <ref-ruling>). Ebenfalls unwesentlich ist, aus welchem Grund die Eheleute die Ehe nach einer zweijährigen Beziehung erst im November 2002 eingegangen sind, denn in jedem Fall bleibt es dabei, dass sie die Ehe in Kenntnis der rechtskräftigen Landesverweisung geschlossen haben. Im Übrigen kann zur vorliegenden Frage auf die Ausführungen im angefochtenen Entscheid verwiesen werden. Die Beschwerde ist auch in diesem Punkt abzuweisen, soweit darauf eingetreten werden kann.
3.3 Wie die Vorinstanz festgestellt hat, ist im vorliegenden Fall entscheidend, dass der Beschwerdeführer und seine neue Ehefrau die Ehe erst nach dem Urteil des Obergerichts geschlossen haben, als die unbedingte Landesverweisung rechtskräftig war. Die Ehefrau habe es im Zeitpunkt des Eheschlusses in Kauf genommen, dass sie ihre Ehe unter Umständen im Ausland leben müsse (angefochtener Entscheid S. 13). Diese tatsächliche Feststellung der Vorinstanz ist für das Bundesgericht im vorliegenden Verfahren verbindlich, da der Beschwerdeführer nicht dartut, dass und inwieweit sie offensichtlich unrichtig sein könnte. Auf seine allgemein gehaltene Behauptung, der "Mechanismus" der Landesverweisung sei für einen Laien "nicht ohne weiteres durchschaubar" (Beschwerde S. 7), ist nicht einzutreten. Unter diesen Umständen ist es nicht von ausschlaggebender Bedeutung, dass die Ehefrau gewisse Schwierigkeiten haben könnte, dem Beschwerdeführer in den Kosovo zu folgen (Urteil 2A.549/2002 vom 12. Februar 2003 E. 3.4 mit Hinweis auf <ref-ruling>). Ebenfalls unwesentlich ist, aus welchem Grund die Eheleute die Ehe nach einer zweijährigen Beziehung erst im November 2002 eingegangen sind, denn in jedem Fall bleibt es dabei, dass sie die Ehe in Kenntnis der rechtskräftigen Landesverweisung geschlossen haben. Im Übrigen kann zur vorliegenden Frage auf die Ausführungen im angefochtenen Entscheid verwiesen werden. Die Beschwerde ist auch in diesem Punkt abzuweisen, soweit darauf eingetreten werden kann.
4. Die Verwaltungsgerichtsbeschwerde ist abzuweisen, soweit darauf einzutreten ist. Mit dem Entscheid in der Sache ist das Gesuch um aufschiebende Wirkung gegenstandslos geworden. Bei diesem Ausgang des Verfahrens hat der Beschwerdeführer die bundesgerichtlichen Kosten zu tragen (Art. 156 Abs. 1 OG).

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Polizei- und Militärdirektion des Kantons Bern und dem Verwaltungsgericht des Kantons Bern sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
Lausanne, 1. Juli 2004
Im Namen des Kassationshofes
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: