No. A Level X card is a "Level Up" card, not an "Evolution card".
An old, pre-DP card would have to say "search for a Basic or Evolution card" in order for you to also be able to search for a Level X.
But Bayleef is from a post-DP set, so it knows to just say "Pokemon" if it means you can search for any type of Pokemon card.
Oh, and you don't get to choose based on the coin flip.
If you win the flip, you go first even if you want to go second.