Qualche tempo fa ci ho sbattuto contro anch'io alla necessita' di creare link da Java.
In realta' il formato dei file lnk non e' propriamente semplice e ovviamente non e' pubblico. L'unica cosa simile ad una specifica (non ufficiale) che trovai e' qui :

http://www.wotsit.org/search.asp

digitando lnk nel campo di ricerca. Se ne ottiene un po' di codice di esempio e un pdf che tratta del reverse engineering del formato.
Io non ho cavato fuori nulla, magari tu sei piu' fortunato.

L'alternativa e' andare via JNI ...