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.