Also, components don't have to be stateful. An element can be viewed as a function invocation which accepts attributes, properties and children and returns DOM. An element which deterministically renders some DOM based only on those inputs is very much like a pure function.
How a custom element produces its DOM nodes are entirely up to it, and several approaches fit with a pure functional view of elements: 1) re-render and replace the entire component DOM, 2) Use a VDOM to patch the component DOM, 3) Use incremental-dom to update the component DOM, and yes 4) template systems like Polymer's can be easily used in a pure functional approach.
The key to being "stateless" isn't in abstracting away the DOM, it's in only using the inputs (attributes, properties, and children) to determine the DOM structure, and only allowing the host of an element to modify inputs so that the element behaves more like a function.
It's similar to mutable object that never modifies its own state, only has public state, and whose methods are pure. Method behavior is fully determined by state that the owner controls.
VirtualDOM is basically that caching mechanism
Poylmer doesn't simplify UI development like React does, the components have to be statefully managed, and always will be because creating/destroying polymer/web components is expensive. The beauty of virtualdom is the previous state doesn't matter in deciding what the new UI should look like, or if a component should be added/removed. Simply render off the current state, which is cheap, and then the previous & current virtualdom is diff'd and applied to the real DOM.
Web components are exciting, and React can leverage it to do CSS sandboxing, though people are already effectively doing this [1]. And the cool thing with declarative programming is we can swap out implementations with more performant ones.
[1] https://github.com/gajus/react-css-modules