I do not have the answer to your question of when paper currency first appeared - a great question. But it is important to point out that acceptance of paper currency took awhile. I am currently transcribing a bit of the Alfred Doten diaries, recollections of a journalist(1829-1903) who maintained a record of his daily experience from 1849 to his death in the early twentieth century. On 2 April 1866 he recalled that the city government of Virginia City, Nevada was switching from "coins" to "greenbacks." He wrote the following:

At City Hall all day – Drew up warrants for salaries & rents for March – Jones signed them, & I issued them – drew my March salary – All salaries paid in Coin, but hereafter will be greenbacks – City on greenback basis for 1st time.

I appended the following note to this description of the transition that was occurring:

People in the American West often preferred coin over paper currency because the former was made of gold or silver while the latter was merely paper that was put forward as legal tenure. In some places and times, paper currency – “greenbacks” – traded for less than the stated value. For this reason, people generally preferred to receive coins in payment because they could then spend them at full value, while merchants often increased the price of something when receiving paper money. By shifting to a “greenback basis” the City was opting for the convenience of paper currency, but this also meant that the actual compensation had been slightly reduced.

As Americans became accustomed to using paper money, the difference in the value vanished, but it is important to remember that even after paper money was introduced it was slow to gain universal acceptance.

edited to reflect excellent comment by /u/tim_mcdaniel

The origins of paper money can be traced back to the "flying money" of 9th century China. Initially issued for private use by merchants, paper currency became popular because it was more convenient to carry sheets of paper than heavy metal coins. The issuing of paper money came under the control of the government by 812 as a means of collecting taxes locally. However, "flying money" is more accurately characterized as bills of credit rather than true paper money, which would gradually emerge later on during the Song dynasty.

Of the various paper notes circulating during the Song dynasty, the most notable is the huizi, which was first issued in 1160 under Emperor Gaozong. However, over-issuing huizi devalued the currency. Emperor Xiaozong, the successor of Gaozong, responded by ordering the exchange of taels of silver for huizi notes. These notes were then destroyed so that the remaining number of circulating notes could appreciate in value. Under Xiaozong's reign, his policies successfully managed to keep inflation in check, which greatly benefited the economy of the Southern Song.

Paper money was adopted by the Jurchen Jin dynasty in 1153, and then by the Yuan dynasty after the Mongols conquered China. Korea started circulating paper money in 1332, Japan in 1334, and Vietnam in 1396. The use of paper money also caught the attention of European travelers, and is described most famously by Marco Polo. In the West, paper money was first issued by Sweden in 1661, the United States in 1690, France in 1720, Russia in 1768, England in 1797, and Germany in 1806.

For further reading, see Tsien Tsuen-hsuin and Joseph Nedham, Science and Civilisation in China, Volume 5: Chemistry and Chemical Technology, Part I: Paper and Printing (New York: Cambridge University Press, 1985). The chapter "Uses of paper and paper products" discusses the history of paper money in detail. I would also recommend the Song dynasty volume in the Cambridge History of China series.