A piece of Lego can be seen as a Polyomino: a plane geometric figure formed by joining one or more equal squares edge to edge.
In Tiling the Plane with a Fixed Number of Polyominoes , Nicolas Ollinger proved that 5 polyominoes are enough to simulate any set of Wang tiles (the shapes of the polyominoes are quite complex and clearly depends on the set of Wang tiles to be simulated). And it is undecidable if a set of Wang tiles can tile the plane (see the link provided by domotorp in his comment).
So it is undecidable given a set of 5 "Lego pieces" (unlimited quantity of each) you can place them (theoretically) on an infinite Lego base and completely cover it (cover the plane).
In other words given a Turing machine, there is a set of 5 lego pieces such that you can cover the whole plane with them if and only if the Turing machine doesn't halt.
But even if you have only 3x1 Lego pieces, and a target object to recreate with them, it can be very hard to find the solution; indeed it is an NP-complete problem as proved in Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson; Tiling Figures of the Plane with Two Bars (1995).