It is known that every polycyclic-by-finite group - even if it admits no affine structure - allows a polynomial structure of bounded degree. A major obstacle to a further development of the theory of these polynomial structures is that the group of the polynomial diffeomorphisms of R-n, in contrast to the group of affine motions, is no longer a finite dimensional Lie group. In this paper we construct a family of (finite dimensional) Lie groups, even linear algebraic groups, of polynomial diffeomorphisms, which we call weighted groups of polynomial diffeomorphisms. It tun-ls out that every polycyclic-by-finite group admits a polynomial structure via these weighted groups; in the nilpotent (and other) case(s), we can sharpen, by specifying a nice set of weights, the existence results obtained in earlier work. We introduce unipotent polynomial structures of nilpotent groups and show how the existence of such polynomial structures is closely related to the existence of simply transitive actions of the corresponding Mal'cev completion. This, and other properties, provide a strong analogy with the situation of affine structures and simply transitive affine actions considered e.g. in the work of Fried, Goldman and Hirsch. Mathematics Subject Classification (1991):57S20, 22E25.