Those two words both seem to be about using a few words/a few steps to do something.
Laconic comes from the ancient word for Sparta, Lakedaemon. The Spartans were noted for lack of verbosity, and what they did say often had a mordant humor to it, which has come to be called a laconic phrase:
A laconic phrase is a very concise or terse statement, named after Laconia (a.k.a. Lacedaemon [Greek Λακεδαίμων]), a polis of ancient Greece (and region of modern Greece) surrounding the city of Sparta proper. In common usage, Sparta referred both to Lacedaemon and Sparta. Similarly, a laconism is a figure of speech in which someone uses very few words to express an idea, in keeping with the Spartan reputation for austerity. This may be used for efficiency (like in military jargon), for philosophical reasons (especially among thinkers who believe in minimalism, such as Stoics), or for better disarming a long, pompous speech (the most famous example being at the Battle of Thermopylae). Spartans were expected to be men of few words, to hold rhetoric in disdain, and to stick to the point. Loquaciousness was seen as a sign of frivolity, and totally unbecoming sensible, down-to-earth Spartan peers.
By the way, the "famous example" referred to is seen farther down the page:
When Leonidas was in charge of guarding the narrow mountain pass at Thermopylae with just 7,000 Greek men in order to delay the invading Persian army, Xerxes offered to spare his men if they gave up their arms. Leonidas replied "Molon labe" (Greek: Μολών λαβέ), which translates to "Come and take them". Today this is the motto of the Greek 1st Army Corps.
Laconic is a synonym of concise, but with a biting quality to it. Think of Calvin Coolidge's response in this case:
Although Coolidge was known to be a skilled and effective public speaker, in private he was a man of few words and was therefore commonly referred to as "Silent Cal." A possibly apocryphal story has it that Dorothy Parker, seated next to him at a dinner, said to him, "Mr. Coolidge, I've made a bet against a fellow who said it was impossible to get more than two words out of you." His famous reply: "You lose."
The New Oxford American Dictionary says, in a note entitled “The Right Word”:
If you don't like to mince words, you'll make every effort to be concise in both your writing and speaking, which means to remove all superfluous details
If you're laconic, you are brief to the point of being curt, brusque, or even uncommunicative
So, being laconic has a more negative connotation. Concise is rather positive.
I believe the difference is in connotation, and Dictionary.com's definitions seem to support this. Concise uses a minimal number of words to express a comprehensive idea. It's trying to inform us without boring us. Laconic, on the other hand, has a bit more personality and is perhaps bordering on insolence in its brevity.
Actually, when I think of laconic, I see James Dean in my mind's eye. Concise -- no James Dean.
The difference between the two words has to do with their directness in expressing ideas. Someone speaking in a laconic manner speaks in riddles or aphorisms, in a very simple style, almost to the point of inscrutability. A quintessential example everyone would be familiar with is Yoda's strange style of speaking when Luke first meets him on Dagobah:
Luke: What's in there?
Yoda: Only what you take with you.
Obviously, Yoda is not directly answering the question Luke really wants answered -- he wants to know the tangible, physical contents of the cave -- but Yoda speaks laconically, in a cryptic style, so as to blunt the young initiate's overeagerness to learn too much before he's ready.
Someone speaking concisely, on the other hand, is trying to pack as much information as possible into his words. This is an example:
The Fourier transform is a unitary change of basis for functions (or distributions) that diagonalizes all convolution operations.
Here, the speaker summarizes a vast theory in a single sentence by using very specialist language, to directly convey a sense of the theory's generality. In general, laconic statements should not be filled with jargon or technical terms, while concise statements as in the above may be.
Merriam-Webster's Dictionary of Synonyms (1984) puts both words in a group that also includes terse, succinct, summary, pithy, and compendious:
concise, terse, succinct, lconic, summary, pithy, compendious are comparable when meaning briefly stated or presented or given to or manifesting brevity in statement or expression. A person is concise who speaks or writes briefly; a thing is concise that is brief because all superfluities have been removed and all elaboration avoided [examples omitted] ... A person or thing is laconic that is characterized by such succinctness as to seem curt, brusque unperturbed, or mystifying [examples omitted]
S.I. Hayakawa, Choose the Right Word: A Modern Guide to Synonyms (1968), however, places concise in a group with compact, compressed, condensed, constricted, dense, solid, and miniaturized, but places laconic in a group with terse, compendious, pithy, sententious, and succinct. Here is Hayakawa on the "compact" family and, more particularly, concise:
These words refer to confinement or weightiness in a relatively small space. ...
Concise, condensed, and compressed suggest progressively greater confinement in space; one use of this progression is to suggest brevity in writing or a lack of wordiness. Concise suggests the use of exactly as many words as are required to express something and no more; it would apply more usually to technical, factual work, but may apply to imaginative prose: [examples omitted].
And here is Hayakawa on the "terse" family and, more particularly, laconic:
These adjectives stress brevity in speech or writing, the avoidance of any wasted words. ... Laconic literally means like a Spartan, with reference to the habitual terseness of Spartan speech. A laconic speaker is so sparing with words as to seem stingy or exceptionally self-controlled. [Examples omitted.] Both a terse and a laconic remark may be so brief as to seem curt. But where a terse remark is complete and its brevity may be due to the pressure of circumstances, a laconic remark may be puzzling and may suggest a deliberate taciturnity: [examples omitted].
In short, both Merriam-Webster and Hayakawa note the fitness of concise to a situation where brevity is appropriate, and view laconic as describing speech that may border on or cross over into rudeness (as curt does). However, Hayakawa also sees laconic as potentially being motivated by a constitutional aversion to lengthy self-expression, whereas concise simply matches the length of the wording to the needs of clarity—and doesn't use a word more.