Hi Deb!
I've been an artist all my life so I hope this will help you. It's what I would do, but others may have better ideas.
I've painted on concrete, stucco, and wood outdoors. I use acrylic patio paints or latex exterior paints. All of them fade eventually which adds to the charm.
In the case of your leaf, since it's small, I would do exactly what you said second. Paint with acrylics, then seal. In a few years if it fades more than you like, repaint it.
Be sure to show us!! I love it!