Hola Victor,
Según la últimos requisitos de certificación para la Tienda Windows (
http://msdn.microsoft.com/en-us/library/windows/apps/hh694083.aspx ), no hay ningún problema con que los anuncios se muestren en una aplicación de pago.
En cualquier caso, no conozco ninguna aplicación que lo haga y no creo que los usuarios estuvieran muy contentos con ninguna App que hiciera eso.
Un saludo.