Не ранее начала XX века. Матрёшку в девяностые годы XIX века придумал Сергей Малютин (прообразом послужила японская игрушка, изображающая бога счастья - Фукурокудзю). Берёза же стала символом России благодаря творчеству тоже Сергея, но уже Есенина. Не могу удержаться от цитирования стихотворения Берестова на эту тему
Чего не знал великий Пушкин?
Не знал он ни одной частушки,
Не видел ни одной матрёшки
В их лакированной одежке.
Берёзу символом Руси
Не звал он, Боже упаси.
Она при нём для этой роли
Не подходила. Ей пороли.
Малютин не имеет никакого отношения к матрешке, как и японцы. Читайте "Подлинная история матрёшки".