There's already underwater powered trenching/laying equipment they use to bury the cables within X miles from the shore. The Baltic Sea is probably shallow enough to bury it all the way across at a higher cost per mile of course.
Plus it could cause damage to environmental ecosystems.